R-Version: [Default] [32-bit] C:\Program Files\R\R-4.1.0


Installieren der Packete

packages <- c("tidyverse", "data.table", "lubridate", "ggplot2", "ggthemes", "recommenderlab", "knitr")

# Noch nicht installierte Pakete installieren
installed_packages <- packages %in% rownames(installed.packages())

if (any(installed_packages == FALSE)) {
  install.packages(packages[!installed_packages])
}

# Laden der Packete
invisible(lapply(packages, library, character.only = TRUE))

# Importieren von Funktionene aus helper file
source("helper.R")

Datenimport

data(MovieLense)
MovieLense
943 x 1664 rating matrix of class ‘realRatingMatrix’ with 99392 ratings.

alle charakter variabeln faktorisieren


movies <- as(MovieLense, "data.frame")
movies <- movies %>% mutate_if(is.character, as.factor)

head(movies)
NA
movies_wider <- pivot_wider(
  movies,
  id_cols = user,
  names_from = item,
  values_from = rating,
  values_fill = NULL,
)

head(movies_wider)

Explorative Datenanalyse

df_1 <- movies %>% group_by(item) %>%  summarize(mean_rating = mean(rating)) %>% sample_n(15) %>% arrange(desc(mean_rating))

ggplot(df_1, aes(y = reorder(item, +mean_rating), x = mean_rating)) +
  geom_col(alpha = 1, fill = 'steelblue') +
  scale_y_discrete(expand = c(0,0)) +
  scale_x_continuous(expand = c(0,0)) +
  geom_text(aes(label=round(mean_rating,2)), hjust = 1.3, color = 'white') +
  labs(
    title = "Durchschnittliche Filmbewertung",
    subtitle = "Zufällige Stichprobe von 15 Filmen",
    y = element_blank(),    x = "Dirchschnittlich Bewertung in Sternen"
  ) +
  theme_classic() +
  theme(axis.text.x = element_blank(),
        axis.ticks.x = element_blank(),
        axis.line.x = element_blank(),
        text = element_text(size = 12) # text size
  )


1. Welches sind die am häufigsten geschauten Genres / Filme?

movies_genre <- MovieLenseMeta %>%
  rename(item = title)
movies_genre$url <- NULL
movies_genre[movies_genre == 0] <- NA
a <- which(movies_genre==1,arr.ind=TRUE)
movies_genre[a] <- names(movies_genre)[a[,"col"]]
movies_genre <- movies_genre %>%
  unite("genres", unknown:Western, sep= ",", 
        remove = TRUE, na.rm = TRUE)
genres<-merge(x=movies,y=movies_genre,by="item",all.x=TRUE)%>%
  mutate(genres = strsplit(as.character(genres), ",")) %>%
  unnest(genres)

df1a <- movies%>%
  group_by(item)%>%
  summarize(count=n())%>%
  ungroup()%>%
  arrange(desc(count))

df1a <- head(df1a, 10)

df1a %>%
  mutate(item = fct_reorder(item, count))%>%
  ggplot(aes(x = count, y = item))+
  geom_col(alpha = 1, fill = 'steelblue')+
  scale_y_discrete(expand = c(0,0)) +
  scale_x_continuous(expand = c(0,0)) +
  geom_text(aes(label=round(count,2)), hjust = 1.3, color = 'white') +
  labs(
    title = "Meist bewertete Filme",
    y = element_blank(),    x = "Anzahl Bewertungen"
  ) +
  theme_classic() +
  theme(axis.text.x = element_blank(),
        axis.ticks.x = element_blank(),
        axis.line.x = element_blank(),
        text = element_text(size = 12) # text size
  )

Da in unserem Datensatz nur die Anzahl Ratings von Filmen gegeben ist, gehen wir davon aus, dass die meist bewerteten, auch die am meist geschauten Filme sind. In der Grafik sieht man die 10 meist bewerteten Filme.

df1b <- genres%>%
  group_by(genres)%>%
  summarize(count=n())%>%
  ungroup()%>%
  arrange(desc(count))

df1b%>%
  mutate(genres = fct_reorder(genres, count))%>%
  ggplot(aes(x = count, y = genres))+
  geom_col(alpha = 1, fill = 'steelblue')+
  scale_y_discrete(expand = c(0,0)) +
  scale_x_continuous(expand = c(0,0)) +
  geom_text(aes(label=count,2), hjust = 1.3, color = 'white') +
  labs(
    title = "Meist bewertete Genres",
    y = element_blank(),    x = "Anzahl Bewertungen"
  ) +
  theme_classic() +
  theme(axis.text.x = element_blank(),
        axis.ticks.x = element_blank(),
        axis.line.x = element_blank(),
        text = element_text(size = 12) # text size
  )

Auch hier wird davon ausgegangen, dass die enres, welche am häufigsten bewertet wurden auch am häufigst geschaut wurden. In der Grafik ist zu sehen, dass Drama das top Genres ist, gefolgt von Comedy und Action.


2. Wie verteilen sich die Kundenratings gesamthaft und nach Genres?

ggplot(movies, aes(x = rating)) +
  geom_bar(alpha = 1, fill = 'steelblue') +
  scale_y_continuous(expand = c(0,0)) +
  scale_x_continuous(expand = c(0,0)) +
  labs(
    title = "Verteilung Kundenratings gesamthaft",
    subtitle = paste("N = ", nrow(movies), " Bewertungen"),
    x = "Kundenbewertungen", 
    y = "Anzahl",
    fill = element_blank()
  ) +
  theme_classic() +
  theme(
    text = element_text(size = 12)
  )

In dieser Grafik ist die Verteilung der bewertungen zu sehen. Die Bewertungen 4 und 5 wirden klar am häufigsten vergeben, wobei 1 und 2 eher selten bewertet werden.

# get rating count per user, add as column for further processing
counts <- movies %>% group_by(user) %>% count()
movies <- merge(movies, counts, by="user")
movies_wider <- merge(movies_wider, counts, by="user")

# avoid users with almost no ratings, use median as threshold
median_count <- median(counts$n)
print(median_count)
[1] 64
# get sample
set.seed(623)
movies_sample <- movies_wider %>% filter(n > median_count) %>% sample_n(5)

# create long table
movies_sample_long <- filter(movies, user %in% movies_sample$user)

# drop item names, 
movies_sample_long <- subset(movies_sample_long, select = -c(item))

df2b <- genres%>%
  group_by(genres)
  
movies_sample_long_grouped <- movies_sample_long %>% group_by(user, rating) %>% summarise(rating_dens = length(user) / first(n), user = first(user), n=first(n), rating = first(rating))
`summarise()` has grouped output by 'user'. You can override using the `.groups` argument.
  
ggplot(genres, aes(x = rating, fill = genres)) +
  geom_bar(alpha = 1, bins = 10) +
  facet_wrap(~genres)+
  scale_y_continuous(expand = c(0,0)) +
  scale_x_continuous(expand = c(0,0)) +
  labs(
    title = "Verteilung Kundenratings nach Genres",
    subtitle = paste("N = ", nrow(movies), " Bewertungen"),
    x = "Durchschnittliche Bewertung", 
    y = "Anzahl",
    fill = element_blank()
  ) +
  theme(
    text = element_text(size = 12),
    legend.position = 'none'
  )
Warning: Ignoring unknown parameters: bins

Hier ist zu sehen, dass das Genres Drama am meisten bewertet wurde, wobei Dokumentationen am wenigsten Bewertungen erhalten haben. Die Bewertungen pro Genres verteilen sich jeweils sehr ähnlich. Die Verteilungen der einzelnen Genres sind ebenfalls ähnlich verteilt wie die bewertungen gesamthaft.


3.Wie verteilen sich die mittleren Kundenratings pro Film?

df3 <- movies %>% 
  group_by(item) %>%  
  summarize(
    mean_rating = mean(rating),
    ratings = n()
  ) %>% 
  mutate(
    more_than_50 = ifelse(ratings >= 50, 'b) mehr als 50 Bewertungen', 'a) weniger als 50 Bewertugen')
  )

ggplot(df3, aes(x = mean_rating)) +
  geom_density(alpha = 1, fill = 'steelblue', bw = 0.08) +
  scale_y_continuous(expand = c(0,0)) +
  scale_x_continuous(expand = c(0,0)) +
  labs(
    title = "Verteilung mittlere Kundenratings pro Film",
    subtitle = paste("N = ", nrow(df3), " Filme"),
    x = "Durchschnittliche Bewertung", 
    y = "Dichte"
  ) +
  theme_classic() +
  theme(text = element_text(size = 12)
  )

In dieser Grafik ist die durchschnittliche Bewertung pro Film zu sehen, wobei auch hier zu sehen ist ,dass die die meisten Filme eine Durchschnittliche Bewertung von ca. 3 - 3.5 haben.

ggplot(df3, aes(x = mean_rating, fill = more_than_50)) +
  geom_density(alpha = 0.5, bw = 0.08) +
  scale_y_continuous(expand = c(0,0)) +
  scale_x_continuous(expand = c(0,0)) +
  labs(
    title = "Verteilung mittlere Kundenratings pro Film",
    subtitle = "N = 1664 Filme",
    x = "Durchschnittliche Bewertung", 
    y = "Dichte",
    fill = element_blank()
  ) +
  theme_classic() +
  theme(
    text = element_text(size = 12),
    legend.position = 'bottom'
  )

Für diese Grafik wurden die Filme in zwei gruppen unterteilt: Filme die weniger als 50 bewertungen erhalten haben, und Filme welche mehr als 50 Bewertungen erhalten haben. In der Grafik ist imernoch die durchschnittliche Bewertung dieser Filme zu sehen wobei deutlich erkannt werden kann, dass filme welche weniger bewertungen erhalten haben, tendenziell auch schlechter bewertet wurden.


4.Wie stark streuen die Ratings von individuellen Kunden?

# Number of ratings per user per rating value
movies_sample_long_grouped <- movies_sample_long %>% group_by(user, rating) %>% summarise(rating_dens = length(user) / first(n), user = first(user), n=first(n), rating = first(rating))
`summarise()` has grouped output by 'user'. You can override using the `.groups` argument.
movies_sample_long_grouped
movies_sample_long

ggplot(movies_sample_long_grouped, aes(x=rating, y = rating_dens, fill=user)) + 
  geom_col(position=position_dodge()) +
  scale_y_continuous(expand = c(0,0)) +
  scale_x_continuous(expand = c(0,0)) +
  labs(
    title = "Streuung Kundenbewertungen für zufällig gewählte Kunden",
    subtitle = "N = 5 Kunden",
    x = "User Bewertung (1-5)", 
    y = "Ausprägung Rating",
    fill = element_blank()
  ) +
  scale_fill_manual("legend", values = c("cyan3", "cyan4", "darkolivegreen3", "darkolivegreen", "coral4")
                    )+
  theme_classic() + 
  theme(
    text = element_text(size = 12),
    legend.position = 'bottom'
  )

In dieser Grafik sehen wir, wie sich die Bewertungen einzelner Kunden verteilen. Auffallend ist generell, dass die Bewertungen 1 und 2 weniger oft abgegeben wurde als 3 und 4. Bei der Verteilung der ratings sind von User zu User Unterschiede feststellbar. User 24 bewertet beispielsweise viel besser als User 639. Dies könnte bedeuten, dass User 24 nur Filme bewertet oder schaut die er/sie mag, oder grundsätzlich höhere Bewertungen abgibt. Leider sehen wir hier weniger gut, welche Tendenzen die Streuung der Rating aller User aufweisen.

movies_span <- movies %>% group_by(user) %>% 
  summarize(mean = mean(rating), min = min(rating), max = max(rating), span = (max(rating) - min(rating)))

movies_span

set.seed(123)

ggplot(sample_n(movies_span, 20), aes(x=user)) +
  geom_point(colour="black", aes(y=mean), shape=21) +
  geom_errorbar(aes(ymin=min, ymax=max)) +
  labs(
    title = "Spannweite Kundenratings ",
    subtitle = "N = 20 Kunden",
    x = "User ID", 
    y = "Rating Range"
  )+
    theme_classic() + 
  theme(
    text = element_text(size = 12),
    legend.position = 'bottom'
  )



ggplot(movies_span, aes(x=user)) +
  geom_bar(colour="black", aes(span)) +
  labs(
    title = "Spannweite Kundenratings",
    subtitle = "",
    x = "Spannweite", 
    y = "Anzahl User"
  )+
    theme_classic() + 
  theme(
    text = element_text(size = 12),
    legend.position = 'bottom'
  )

NA

0In diesen Grafiken sehen wir detailliertere Informationen über die Spannweite und den Mittelpunkt. In der ersten Übersicht ist die Spannweite und der Mittelpunkt einzelner Kunden dargestellt. Es fällt auf, dass trotz des teilweise relativ hohem Mittelwert alle Ratings von 1-5 abgegeben wurden. Ein rating von 5 wurde sozusagen immer abgegeben, 1 nicht immer. In der zweiten Übersicht ist die Spannweite aller Kunden dargestellt. Hier wird sichtbar, dass die meisten Kunden Bewertungen von 1-5 abgegeben haben (Spannweite=4), und nur weinige sehr homogen bewertet haben (Spannweite = 1-2). Eine kleine Spannweite kann hier auch aufgetreten sein, da diese User sehr wenige Bewertungen abgegeben haben.


5.Welchen Einfluss hat die Normierung der Ratings pro Kunde auf deren Verteilung?

hist(getRatings(MovieLense), 
     breaks=15,
     main = "Verteilung der Bewertungen")

#hist(getRatings(MovieLenseNorm), breaks=40)

Die Ratings sind nun ungefähr Normalverteilt mit einem Durchschnittsrating von 0 und einer Standardabweichung von 1. Erkennbar ist, dass die Verteilung rechtssteil und linksschief ist, also mehrheitlich positive Bewertungen abgegeben wurden. Durch die Normierung der Daten werden die Ratings jedes Users auf dieselbe Verteilung gestaucht, wodurch man die Verteilung aller Daten analysieren kann. Dadurch hat man beispielsweise die Möglichkeit die durchschnittliche Bewertungstendenz herauszufinden.


6.Welche strukturellen Charakteristika (z.B. Sparsity) und Auffälligkeiten zeigt die User Item Matrix?

image(MovieLense, main = "Raw Ratings")


MovieLenseNorm <- normalize(MovieLense, method="Z-score")
image(MovieLenseNorm, main = "Normalized Ratings")

Users mit tiefen ID’s und Filme mit hohen ID’s weisen weniger ratings auf. Filme mit tiefer ID jedoch sehr viele. Auffallend ist, dass es einige wenige User gibt, die fast alle Filme bewertet haben (erkennbar durch die horizontalen scharzen Striche). Dies scheinen sehr aktive Bewerter zu sein. Viele Users haben jedoch nur einen kleinen Teil der Filme bewertet. Bei den Filmen ist eine ähnliche Tendenz wahrzunehmen, jedoch sind die vertikalen Striche breiter. Möglicherweise sind dort einige beliebte Filme zusammengefasst.


Datenreduktion

get_sparsity <- function(Matrix) {
  round(( 1 - (nratings(Matrix) / (dim(Matrix)[1] * dim(Matrix)[2]))) * 100,2)
}

show_sparsity <- function(Matrix, Name) {

  Measurement <- list('Matrix','Dimension', 'Sparsity', 'Density')
  Value <- list(Name, paste('(',toString(dim(Matrix)), ')'),paste(get_sparsity(Matrix), '%' ), paste(100 - get_sparsity(Matrix), '%' ))
  df <- cbind(Measurement,Value)
  head(df)
}

show_sparsity_change <- function(oldMatrix, newMatrix) {
  print(list(show_sparsity(oldMatrix, 'Old Matrix'), show_sparsity(newMatrix, 'New Matrix')))
  
  
}

show_sparsity_change(MovieLense, ratingMatrix)
[[1]]
     Measurement Value          
[1,] "Matrix"    "Old Matrix"   
[2,] "Dimension" "( 943, 1664 )"
[3,] "Sparsity"  "93.67 %"      
[4,] "Density"   "6.33 %"       

[[2]]
     Measurement Value         
[1,] "Matrix"    "New Matrix"  
[2,] "Dimension" "( 400, 700 )"
[3,] "Sparsity"  "75.8 %"      
[4,] "Density"   "24.2 %"      
old_matrix <- as(MovieLense, "data.frame") %>% 
  group_by(item) %>%  
  summarize(
    mean_rating = mean(rating),
    ratings = n()
  ) %>% 
  mutate(
    matrix = 'a) alte Matrix'
  )

new_matrix <- as(ratingMatrix, "data.frame") %>% 
  group_by(item) %>%  
  summarize(
    mean_rating = mean(rating),
    ratings = n()
  ) %>% 
  mutate(
    matrix = 'b) neue Matrix'
  )

comparison <- bind_rows(old_matrix, new_matrix)

ggplot(comparison, aes(x = mean_rating, fill = matrix)) +
  geom_density(alpha = 0.5, bw = 0.08) +
  scale_y_continuous(expand = c(0,0)) +
  scale_x_continuous(expand = c(0,0)) +
  labs(
    title = "Verteilung mittlere Kundenratings pro Film",
    subtitle = "N = 1664 Filme",
    x = "Durchschnittliche Bewertung", 
    y = "Dichte",
    fill = element_blank()
  ) +
  theme_classic() +
  theme(
    text = element_text(size = 12),
    legend.position = c(.90, .95)
  )

image(ratingMatrix, main = "Raw Ratings")


Analyse Ähnlichkeitsmatrix

1. Zerlege den reduzierten MovieLense Datensatz in ein disjunktes Trainings- und Testdatenset im Verhältnis 4:1

#split <- rowCount(ratingMatrix) * 0.75
# train <- ratingMatrix[1:300]
# test <- ratingMatrix[301:400]

# train-test split 
set.seed(42)
data <- as(ratingMatrix, "data.frame")
df <- data %>% group_by(user) %>% summarize(mean_rating = mean(rating))

df <- sample_frac(df, size = 0.8, replace = FALSE)
df_train <- semi_join(data,df,by='user')
df_test <- anti_join(data,df_train,by='user')
train <- as(df_train, "realRatingMatrix")
test <- as(df_test, 'realRatingMatrix')

dim(train)
[1] 320 700
dim(test)
[1]  80 700

2. Trainiere ein IBCF Modell mit 30 Nachbarn und Cosine Similarity


rec <- Recommender(train, method = "IBCF", param=list(method="Cosine", k=30, normalize = NULL, na_as_zero = TRUE)) #normalize = 'center'
rec
Recommender of type ‘IBCF’ for ‘realRatingMatrix’ 
learned using 320 users.
# predict top 10 movies for 100 users
pre <- predict(rec, test, n = 10)
pre
Recommendations as ‘topNList’ with n = 10 for 80 users. 
reco_list <- as(pre, "list")

# top 10 recommendations for the 13th user in reco_list
reco_list[13]
$`254`
 [1] "Belle de jour (1967)"                      "Three Colors: Red (1994)"                  "Unbearable Lightness of Being, The (1988)"
 [4] "Wings of Desire (1987)"                    "Piano, The (1993)"                         "Jackal, The (1997)"                       
 [7] "Eve's Bayou (1997)"                        "Devil's Advocate, The (1997)"              "Cat on a Hot Tin Roof (1958)"             
[10] "Charade (1963)"                           
#image(as(pre, "matrix"))

3. Bestimme die Verteilung der Filme, welche bei IBCF für paarweise Ähnlichkeitsvergleiche verwendet werden

model <- getModel(rec)
colSum <- colSums(model$sim > 0)

df <- as.data.frame(colSum)

# add index column
df <- cbind(item = rownames(df), df)
rownames(df) <- 1:nrow(df)

ggplot(df, aes(x = colSum)) +
  geom_density(alpha = 1, fill = 'steelblue', bw = 4) +
  scale_y_continuous(expand = c(0,0)) +
  scale_x_continuous(expand = c(0,0)) +
  labs(
    title = "Verteilung der Anzahl ähnlicher Filme",
    # subtitle = paste("N = ", nrow(df3), " Filme"),
    x = "Häufigkeit zu der der Film als Nachbar auftaucht", 
    y = "Häufigkeit"
  ) +
  theme_classic() +
  theme(text = element_text(size = 12)
  )


4. Bestimme die Filme, die am häufigsten in der Cosine-Ähnlichkeitsmatrix auftauchen und analysiere deren Vorkommen und Ratings im reduzierten Datensatz

df1 <- df %>% arrange(desc(colSum)) %>% head(10)
df1

ggplot(df1, aes(x = colSum, y = reorder(item, +colSum)))+
  geom_col(alpha = 1, fill = 'steelblue')+
  scale_y_discrete(expand = c(0,0)) +
  scale_x_continuous(expand = c(0,0)) +
  geom_text(aes(label=round(colSum,2)), hjust = 1.3, color = 'white') +
  labs(
    title = "Häufigste Filme in Cosine-Ähnlichkeitsmatrix",
    y = element_blank(),
    x = "Anzahl Filme in deren Nachbarschaft der Film ist"
  ) +
  theme_classic() +
  theme(axis.text.x = element_blank(),
        axis.ticks.x = element_blank(),
        axis.line.x = element_blank(),
        text = element_text(size = 12) # text size
  )

top10 <- as.list(df1)$item

data <- as(ratingMatrix, "data.frame")
data1 <- data %>%
  group_by(item) %>%
  summarize(mean_rating = mean(rating)) %>%
  arrange(desc(mean_rating)) %>%
  mutate(category = ifelse(item %in% top10, 'Häufigste 10 Filme', 'Restliche Filme'))

ggplot(data1, aes(x = mean_rating, fill = category)) +
  geom_density(alpha = 0.5, bw = 0.05) +
  scale_y_continuous(expand = c(0,0)) +
  scale_x_continuous(expand = c(0,0)) +
  labs(
    title = "Verteilung mittlere Kundenratings pro Film",
    x = "Durchschnittliche Bewertung",
    y = "Dichte",
    fill = element_blank()
  ) +
  theme_classic() +
  theme(
    text = element_text(size = 12),
    legend.position = c(.14, .93)
  )


Implementierung Top-N Metriken

show_precision <- function(listOfDifferentN, ratingMatrix, threshold) {
  
  # normalize the rating matrix
  ratingMatrix <- normalize(ratingMatrix, method="Z-score", row=TRUE)
  
  # create a training set and a test set with true positives for recall and precision
  data <- as(ratingMatrix, "data.frame")
  relevant <- data %>% group_by(user) %>% sample_n(30)
  true_positives <- relevant %>% filter(rating >= threshold)
  false_positives <- relevant %>% filter(rating < threshold)
  
  # remove testing observations from training set
  train <- anti_join(data, relevant,by=c('user','item'))
  train <- as(train, 'realRatingMatrix')
  
  # train model based on training set
  rec <- Recommender(train, method = "IBCF", param=list(method="Cosine", k=30, normalize = NULL, na_as_zero = TRUE)) #normalize = 'center', 'Z-score'
  
  for (N in listOfDifferentN) {

    # predict top N movies
    pre <- predict(rec, train, n = N)
    reco_list <- as(pre, "list")
    recommendations <- as.data.frame(reco_list)
    
    # find true positives and false positives for all users and add them up
    true_total <- 0
    false_total <- 0
    for (i in as.list(unique(true_positives['user']))$user) {
      our_user <- paste('X', i, sep = '')
      recommendations['item'] <- recommendations[our_user]

      true_total <- true_total + nrow(inner_join(recommendations['item'], true_positives %>% filter(user == as.integer(i)), by = 'item'))
      false_total <- false_total + nrow(inner_join(recommendations['item'], false_positives %>% filter(user == as.integer(i)), by = 'item'))
    }
    
    # print Summary
    print(paste('N =', N))
    print(paste('Number of True Positives:',true_total))
    print(paste('Number of False Positives:',false_total))
    print(paste('Precision:',true_total / (true_total + false_total)))
    print('')
  }
}

show_precision(c(5,10,15,20,25,30), ratingMatrix, 0)
[1] "N = 5"
[1] "Number of True Positives: 68"
[1] "Number of False Positives: 24"
[1] "Precision: 0.739130434782609"
[1] ""
[1] "N = 10"
[1] "Number of True Positives: 162"
[1] "Number of False Positives: 45"
[1] "Precision: 0.782608695652174"
[1] ""
[1] "N = 15"
[1] "Number of True Positives: 274"
[1] "Number of False Positives: 66"
[1] "Precision: 0.805882352941176"
[1] ""
[1] "N = 20"
[1] "Number of True Positives: 403"
[1] "Number of False Positives: 105"
[1] "Precision: 0.793307086614173"
[1] ""
[1] "N = 25"
[1] "Number of True Positives: 515"
[1] "Number of False Positives: 135"
[1] "Precision: 0.792307692307692"
[1] ""
[1] "N = 30"
[1] "Number of True Positives: 632"
[1] "Number of False Positives: 177"
[1] "Precision: 0.781211372064277"
[1] ""

Catalog coverage

rec <- Recommender(train, method = "IBCF", param=list(method="Cosine", k=30, normalize = NULL, na_as_zero = TRUE)) #normalize = 'center', 'Z-score'

show_coverage <- function(listOfDifferentN, recommender) {
  
  listOfCoverages <- vector()
  for (N in listOfDifferentN) {

    # predict top N movies
    pre <- predict(rec, train, n = N)
    reco_list <- as(pre, "list")
    recommendations <- as.data.frame(reco_list)
    all_recommendations <- list()
    
    # find true positives and false positives for all users and add them up
    for (i in colnames(recommendations)) {
      all_recommendations <- append(all_recommendations, dplyr::pull(recommendations[i]))

    }

    
    listOfCoverages <- c(listOfCoverages, round(length(unique(all_recommendations)) / dim(train)[2], digits = 4))
  }
  return (data.frame(N = listOfDifferentN, coverage = listOfCoverages))
}

df_coverage <- show_coverage(c(5,10,15,20,25,30), rec)
df_coverage

Summe aller unterschiedlichen Produkte, welche in den Top-N Listen aller Kund*Innen ingesamt auftauchen dividiert durch die Menge aller Produkte.


System-level novelty

# train recommender
rec <- Recommender(train, method = "IBCF", param=list(method="Cosine", k=30, normalize = NULL, na_as_zero = TRUE))


show_novelty <- function(listOfDifferentN, recommender) {
  # create a dataset wit calculated popularity for every movie
  popularity <- as(MovieLense, "data.frame")
  popularity <- popularity %>%
    group_by(item) %>% 
    summarize(ratings = n() / dim(MovieLense)[2]) %>% 
    mutate(ratings = log2(ratings))
  
  listOfNovelties <- vector()
  for (N in listOfDifferentN) {
    # get top-N-list for a certain N
    pre <- predict(rec, train, n = N)
    reco_list <- as(pre, "list")
    recommendations <- as.data.frame(reco_list)
    
    
    total_novelty <- vector()
    for (i in colnames(recommendations)) {
      # calculate mean popularity of recommended items for user
      reco <- recommendations[i]
      colnames(reco)[1] <- "item"
      reco <- inner_join(popularity, reco, by = 'item')
      novelty <- mean(as.numeric(reco$ratings))
      total_novelty <- c(total_novelty, novelty)
    }
    listOfNovelties <- c(listOfNovelties, 0 - mean(total_novelty))
  }
return (data.frame(N = listOfDifferentN, novelty = listOfNovelties))
}

df_novelty <- show_novelty(c(5,10,15,20,25,30), rec)
df_novelty

Mittel der Shannon Information der Popularität der Produkte in der Top-N Liste gemittelt über alle Kund*Innen.


image(as(rec@model$sim, "realRatingMatrix"))

#similarity

#image(as(similarity(train, method = "Cosine", which = "items"), "matrix"))

# plotSimilarityMatrix(train, y = NULL, clusLabels = NULL, colX = NULL, colY = NULL, myLegend = NULL, fileName = "posteriorSimilarityMatrix", savePNG = FALSE, semiSupervised = FALSE, showObsNames = FALSE, clr = FALSE, clc = FALSE, plotWidth = 500, plotHeight = 450)

cosine_sim <- function(A, B)
{
  similarity <- A %*% B / (norm(A, type="2") * norm(B, type="2"))
  return(similarity)
}

jaccard_sim <- function(A, B)
{
  inter = length(intersect(A, B))
  union = length(A) + length(B) - inter
  jac = inter / union
  return (jac)
}


A <- c(5, 3, 2, 1)
B <- c(1, 2, 3, 4)

cosine_sim(A, B)
          [,1]
[1,] 0.6139406
jaccard_sim(A, B)
[1] 0.6
#library(lsa)
#cosine(A, B)
similarity <- as.matrix(rec@model$sim)
dim(similarity)
[1] 700 700
wide_matrix <- as.matrix(subset(movies_wider, select = -c(user)))

# replace nas with 0 (no adjusted cosine similarity)
wide_matrix[is.na(wide_matrix)] <- 0

# ibcf, because columns are taken here
# row count
len <- dim(wide_matrix)[2]
res <- diag(len)

for(i in 1:len)
{
  for(j in 1:len)
  {
    if(i < j & i != j)
    {
      res[i,j] <- cosine_sim(wide_matrix[,i], wide_matrix[,j])
      res[j,i] <- res[i,j]
    }
  }
}
res[1:10, 1:10]
           [,1]       [,2]      [,3]       [,4]       [,5]       [,6]      [,7]       [,8]      [,9]      [,10]
 [1,] 1.0000000 0.40238218 0.3302448 0.45493792 0.28671351 0.11634398 0.6209786 0.48111389 0.4962884 0.27393511
 [2,] 0.4023822 1.00000000 0.2730692 0.50257077 0.31883618 0.08356281 0.3834034 0.33700186 0.2552520 0.17108221
 [3,] 0.3302448 0.27306918 1.0000000 0.32486639 0.21295656 0.10672227 0.3729207 0.20079389 0.2736693 0.15810426
 [4,] 0.4549379 0.50257077 0.3248664 1.00000000 0.33423948 0.09030829 0.4892828 0.49023553 0.4190436 0.25256072
 [5,] 0.2867135 0.31883618 0.2129566 0.33423948 1.00000000 0.03729866 0.3347686 0.25916097 0.2724484 0.05545322
 [6,] 0.1163440 0.08356281 0.1067223 0.09030829 0.03729866 1.00000000 0.1396166 0.08387647 0.1510645 0.20309700
 [7,] 0.6209786 0.38340339 0.3729207 0.48928280 0.33476858 0.13961658 1.0000000 0.42351452 0.5274623 0.31862281
 [8,] 0.4811139 0.33700186 0.2007939 0.49023553 0.25916097 0.08387647 0.4235145 1.00000000 0.4244289 0.26776402
 [9,] 0.4962884 0.25525203 0.2736693 0.41904357 0.27244840 0.15106449 0.5274623 0.42442894 1.0000000 0.28851441
[10,] 0.2739351 0.17108221 0.1581043 0.25256072 0.05545322 0.20309700 0.3186228 0.26776402 0.2885144 1.00000000
#dim(wide_matrix)
#cosine_sim(wide_matrix[,1], wide_matrix[,2])
#wide_matrix[2,1]
#as.matrix(subset(movies_wider, select = -c(user)))[,2]

df_res <- as.data.frame(res)
df_res

image(as(df_res, "realRatingMatrix"))

as(df_test, 'realRatingMatrix')
80 x 700 rating matrix of class ‘realRatingMatrix’ with 14486 ratings.
#ggplot(df_res, aes(x = x_variable, y = y_variable)) + stat_density2d(aes(fill = ..density..), contour = F, geom = 'tile')
#ggplot(df_res, aes(x=V1, y=V2) ) +
#  geom_bin2d() +
#  theme_bw()
require(lattice)
Loading required package: lattice
levelplot(res)

wide_matrix <- as.matrix(subset(movies_wider, select = -c(user)))

# replace nas with 0 (no adjusted cosine similarity)
#wide_matrix[is.na(wide_matrix)] <- 0

# ibcf, because columns are taken here
# row count
len <- dim(wide_matrix)[2]
res <- diag(len)

for(i in 1:len)
{
  for(j in 1:len)
  {
    if(i < j & i != j)
    {
      res[i,j] <- jaccard_sim(wide_matrix[,i], wide_matrix[,j])
      res[j,i] <- res[i,j]
    }
  }
}
SPielwiese
LS0tDQp0aXRsZTogIkNvbGxhYm9yYXRpdmUgTW92aWUgUmVjb21tZW5kZXIiDQphdXRob3I6ICJQYXNjYWwgQmVyZ2VyLCBMZWEgQsO8dGxlciAmIEpvw6tsIEdyb3NqZWFuIg0Kb3V0cHV0Og0KICBodG1sX25vdGVib29rOiBkZWZhdWx0DQogIHBkZl9kb2N1bWVudDogZGVmYXVsdA0KLS0tDQpSLVZlcnNpb246ICoqW0RlZmF1bHRdIFszMi1iaXRdIEM6XFxQcm9ncmFtIEZpbGVzXFxSXFxSLTQuMS4wKioNCg0KKioqIA0KIyMgSW5zdGFsbGllcmVuIGRlciBQYWNrZXRlDQpgYGB7ciBtZXNzYWdlPUZBTFNFLCB3YXJuaW5nPUZBTFNFfQ0KcGFja2FnZXMgPC0gYygidGlkeXZlcnNlIiwgImRhdGEudGFibGUiLCAibHVicmlkYXRlIiwgImdncGxvdDIiLCAiZ2d0aGVtZXMiLCAicmVjb21tZW5kZXJsYWIiLCAia25pdHIiKQ0KDQojIE5vY2ggbmljaHQgaW5zdGFsbGllcnRlIFBha2V0ZSBpbnN0YWxsaWVyZW4NCmluc3RhbGxlZF9wYWNrYWdlcyA8LSBwYWNrYWdlcyAlaW4lIHJvd25hbWVzKGluc3RhbGxlZC5wYWNrYWdlcygpKQ0KDQppZiAoYW55KGluc3RhbGxlZF9wYWNrYWdlcyA9PSBGQUxTRSkpIHsNCiAgaW5zdGFsbC5wYWNrYWdlcyhwYWNrYWdlc1shaW5zdGFsbGVkX3BhY2thZ2VzXSkNCn0NCg0KIyBMYWRlbiBkZXIgUGFja2V0ZQ0KaW52aXNpYmxlKGxhcHBseShwYWNrYWdlcywgbGlicmFyeSwgY2hhcmFjdGVyLm9ubHkgPSBUUlVFKSkNCg0KIyBJbXBvcnRpZXJlbiB2b24gRnVua3Rpb25lbmUgYXVzIGhlbHBlciBmaWxlDQpzb3VyY2UoImhlbHBlci5SIikNCmBgYA0KDQoqKioNCiMjIERhdGVuaW1wb3J0DQpgYGB7cn0NCmRhdGEoTW92aWVMZW5zZSkNCk1vdmllTGVuc2UNCmBgYA0KDQoqKioNCiMjIyMgYWxsZSBjaGFyYWt0ZXIgdmFyaWFiZWxuIGZha3RvcmlzaWVyZW4NCmBgYHtyfQ0KDQptb3ZpZXMgPC0gYXMoTW92aWVMZW5zZSwgImRhdGEuZnJhbWUiKQ0KbW92aWVzIDwtIG1vdmllcyAlPiUgbXV0YXRlX2lmKGlzLmNoYXJhY3RlciwgYXMuZmFjdG9yKQ0KDQpoZWFkKG1vdmllcykNCg0KYGBgDQoNCmBgYHtyfQ0KbW92aWVzX3dpZGVyIDwtIHBpdm90X3dpZGVyKA0KICBtb3ZpZXMsDQogIGlkX2NvbHMgPSB1c2VyLA0KICBuYW1lc19mcm9tID0gaXRlbSwNCiAgdmFsdWVzX2Zyb20gPSByYXRpbmcsDQogIHZhbHVlc19maWxsID0gTlVMTCwNCikNCg0KaGVhZChtb3ZpZXNfd2lkZXIpDQpgYGANCg0KKioqDQojIyBFeHBsb3JhdGl2ZSBEYXRlbmFuYWx5c2UNCmBgYHtyfQ0KZGZfMSA8LSBtb3ZpZXMgJT4lIGdyb3VwX2J5KGl0ZW0pICU+JSAgc3VtbWFyaXplKG1lYW5fcmF0aW5nID0gbWVhbihyYXRpbmcpKSAlPiUgc2FtcGxlX24oMTUpICU+JSBhcnJhbmdlKGRlc2MobWVhbl9yYXRpbmcpKQ0KDQpnZ3Bsb3QoZGZfMSwgYWVzKHkgPSByZW9yZGVyKGl0ZW0sICttZWFuX3JhdGluZyksIHggPSBtZWFuX3JhdGluZykpICsNCiAgZ2VvbV9jb2woYWxwaGEgPSAxLCBmaWxsID0gJ3N0ZWVsYmx1ZScpICsNCiAgc2NhbGVfeV9kaXNjcmV0ZShleHBhbmQgPSBjKDAsMCkpICsNCiAgc2NhbGVfeF9jb250aW51b3VzKGV4cGFuZCA9IGMoMCwwKSkgKw0KICBnZW9tX3RleHQoYWVzKGxhYmVsPXJvdW5kKG1lYW5fcmF0aW5nLDIpKSwgaGp1c3QgPSAxLjMsIGNvbG9yID0gJ3doaXRlJykgKw0KICBsYWJzKA0KICAgIHRpdGxlID0gIkR1cmNoc2Nobml0dGxpY2hlIEZpbG1iZXdlcnR1bmciLA0KICAgIHN1YnRpdGxlID0gIlp1ZsOkbGxpZ2UgU3RpY2hwcm9iZSB2b24gMTUgRmlsbWVuIiwNCiAgICB5ID0gZWxlbWVudF9ibGFuaygpLCAgICB4ID0gIkRpcmNoc2Nobml0dGxpY2ggQmV3ZXJ0dW5nIGluIFN0ZXJuZW4iDQogICkgKw0KICB0aGVtZV9jbGFzc2ljKCkgKw0KICB0aGVtZShheGlzLnRleHQueCA9IGVsZW1lbnRfYmxhbmsoKSwNCiAgICAgICAgYXhpcy50aWNrcy54ID0gZWxlbWVudF9ibGFuaygpLA0KICAgICAgICBheGlzLmxpbmUueCA9IGVsZW1lbnRfYmxhbmsoKSwNCiAgICAgICAgdGV4dCA9IGVsZW1lbnRfdGV4dChzaXplID0gMTIpICMgdGV4dCBzaXplDQogICkNCmBgYA0KDQoqKioNCiMjIyMgMS4gV2VsY2hlcyBzaW5kIGRpZSBhbSBow6R1Zmlnc3RlbiBnZXNjaGF1dGVuIEdlbnJlcyAvIEZpbG1lPw0KYGBge3J9DQptb3ZpZXNfZ2VucmUgPC0gTW92aWVMZW5zZU1ldGEgJT4lDQogIHJlbmFtZShpdGVtID0gdGl0bGUpDQptb3ZpZXNfZ2VucmUkdXJsIDwtIE5VTEwNCm1vdmllc19nZW5yZVttb3ZpZXNfZ2VucmUgPT0gMF0gPC0gTkENCmEgPC0gd2hpY2gobW92aWVzX2dlbnJlPT0xLGFyci5pbmQ9VFJVRSkNCm1vdmllc19nZW5yZVthXSA8LSBuYW1lcyhtb3ZpZXNfZ2VucmUpW2FbLCJjb2wiXV0NCm1vdmllc19nZW5yZSA8LSBtb3ZpZXNfZ2VucmUgJT4lDQogIHVuaXRlKCJnZW5yZXMiLCB1bmtub3duOldlc3Rlcm4sIHNlcD0gIiwiLCANCiAgICAgICAgcmVtb3ZlID0gVFJVRSwgbmEucm0gPSBUUlVFKQ0KZ2VucmVzPC1tZXJnZSh4PW1vdmllcyx5PW1vdmllc19nZW5yZSxieT0iaXRlbSIsYWxsLng9VFJVRSklPiUNCiAgbXV0YXRlKGdlbnJlcyA9IHN0cnNwbGl0KGFzLmNoYXJhY3RlcihnZW5yZXMpLCAiLCIpKSAlPiUNCiAgdW5uZXN0KGdlbnJlcykNCg0KZGYxYSA8LSBtb3ZpZXMlPiUNCiAgZ3JvdXBfYnkoaXRlbSklPiUNCiAgc3VtbWFyaXplKGNvdW50PW4oKSklPiUNCiAgdW5ncm91cCgpJT4lDQogIGFycmFuZ2UoZGVzYyhjb3VudCkpDQoNCmRmMWEgPC0gaGVhZChkZjFhLCAxMCkNCg0KZGYxYSAlPiUNCiAgbXV0YXRlKGl0ZW0gPSBmY3RfcmVvcmRlcihpdGVtLCBjb3VudCkpJT4lDQogIGdncGxvdChhZXMoeCA9IGNvdW50LCB5ID0gaXRlbSkpKw0KICBnZW9tX2NvbChhbHBoYSA9IDEsIGZpbGwgPSAnc3RlZWxibHVlJykrDQogIHNjYWxlX3lfZGlzY3JldGUoZXhwYW5kID0gYygwLDApKSArDQogIHNjYWxlX3hfY29udGludW91cyhleHBhbmQgPSBjKDAsMCkpICsNCiAgZ2VvbV90ZXh0KGFlcyhsYWJlbD1yb3VuZChjb3VudCwyKSksIGhqdXN0ID0gMS4zLCBjb2xvciA9ICd3aGl0ZScpICsNCiAgbGFicygNCiAgICB0aXRsZSA9ICJNZWlzdCBiZXdlcnRldGUgRmlsbWUiLA0KICAgIHkgPSBlbGVtZW50X2JsYW5rKCksICAgIHggPSAiQW56YWhsIEJld2VydHVuZ2VuIg0KICApICsNCiAgdGhlbWVfY2xhc3NpYygpICsNCiAgdGhlbWUoYXhpcy50ZXh0LnggPSBlbGVtZW50X2JsYW5rKCksDQogICAgICAgIGF4aXMudGlja3MueCA9IGVsZW1lbnRfYmxhbmsoKSwNCiAgICAgICAgYXhpcy5saW5lLnggPSBlbGVtZW50X2JsYW5rKCksDQogICAgICAgIHRleHQgPSBlbGVtZW50X3RleHQoc2l6ZSA9IDEyKSAjIHRleHQgc2l6ZQ0KICApDQpgYGANCkRhIGluIHVuc2VyZW0gRGF0ZW5zYXR6IG51ciBkaWUgQW56YWhsIFJhdGluZ3Mgdm9uIEZpbG1lbiBnZWdlYmVuIGlzdCwgZ2VoZW4gd2lyIGRhdm9uIGF1cywgZGFzcyBkaWUgbWVpc3QgYmV3ZXJ0ZXRlbiwgYXVjaCBkaWUgYW0gbWVpc3QgZ2VzY2hhdXRlbiBGaWxtZSBzaW5kLiBJbiBkZXIgR3JhZmlrIHNpZWh0IG1hbiBkaWUgMTAgbWVpc3QgYmV3ZXJ0ZXRlbiBGaWxtZS4NCg0KYGBge3J9DQpkZjFiIDwtIGdlbnJlcyU+JQ0KICBncm91cF9ieShnZW5yZXMpJT4lDQogIHN1bW1hcml6ZShjb3VudD1uKCkpJT4lDQogIHVuZ3JvdXAoKSU+JQ0KICBhcnJhbmdlKGRlc2MoY291bnQpKQ0KDQpkZjFiJT4lDQogIG11dGF0ZShnZW5yZXMgPSBmY3RfcmVvcmRlcihnZW5yZXMsIGNvdW50KSklPiUNCiAgZ2dwbG90KGFlcyh4ID0gY291bnQsIHkgPSBnZW5yZXMpKSsNCiAgZ2VvbV9jb2woYWxwaGEgPSAxLCBmaWxsID0gJ3N0ZWVsYmx1ZScpKw0KICBzY2FsZV95X2Rpc2NyZXRlKGV4cGFuZCA9IGMoMCwwKSkgKw0KICBzY2FsZV94X2NvbnRpbnVvdXMoZXhwYW5kID0gYygwLDApKSArDQogIGdlb21fdGV4dChhZXMobGFiZWw9Y291bnQsMiksIGhqdXN0ID0gMS4zLCBjb2xvciA9ICd3aGl0ZScpICsNCiAgbGFicygNCiAgICB0aXRsZSA9ICJNZWlzdCBiZXdlcnRldGUgR2VucmVzIiwNCiAgICB5ID0gZWxlbWVudF9ibGFuaygpLCAgICB4ID0gIkFuemFobCBCZXdlcnR1bmdlbiINCiAgKSArDQogIHRoZW1lX2NsYXNzaWMoKSArDQogIHRoZW1lKGF4aXMudGV4dC54ID0gZWxlbWVudF9ibGFuaygpLA0KICAgICAgICBheGlzLnRpY2tzLnggPSBlbGVtZW50X2JsYW5rKCksDQogICAgICAgIGF4aXMubGluZS54ID0gZWxlbWVudF9ibGFuaygpLA0KICAgICAgICB0ZXh0ID0gZWxlbWVudF90ZXh0KHNpemUgPSAxMikgIyB0ZXh0IHNpemUNCiAgKQ0KYGBgDQpBdWNoIGhpZXIgd2lyZCBkYXZvbiBhdXNnZWdhbmdlbiwgZGFzcyBkaWUgZW5yZXMsIHdlbGNoZSBhbSBow6R1Zmlnc3RlbiBiZXdlcnRldCB3dXJkZW4gYXVjaCBhbSBow6R1Zmlnc3QgZ2VzY2hhdXQgd3VyZGVuLiBJbiBkZXIgR3JhZmlrIGlzdCB6dSBzZWhlbiwgZGFzcyBEcmFtYSBkYXMgdG9wIEdlbnJlcyBpc3QsIGdlZm9sZ3Qgdm9uIENvbWVkeSB1bmQgQWN0aW9uLg0KDQoqKioNCiMjIyMgMi4gV2llIHZlcnRlaWxlbiBzaWNoIGRpZSBLdW5kZW5yYXRpbmdzIGdlc2FtdGhhZnQgdW5kIG5hY2ggR2VucmVzPw0KYGBge3J9DQpnZ3Bsb3QobW92aWVzLCBhZXMoeCA9IHJhdGluZykpICsNCiAgZ2VvbV9iYXIoYWxwaGEgPSAxLCBmaWxsID0gJ3N0ZWVsYmx1ZScpICsNCiAgc2NhbGVfeV9jb250aW51b3VzKGV4cGFuZCA9IGMoMCwwKSkgKw0KICBzY2FsZV94X2NvbnRpbnVvdXMoZXhwYW5kID0gYygwLDApKSArDQogIGxhYnMoDQogICAgdGl0bGUgPSAiVmVydGVpbHVuZyBLdW5kZW5yYXRpbmdzIGdlc2FtdGhhZnQiLA0KICAgIHN1YnRpdGxlID0gcGFzdGUoIk4gPSAiLCBucm93KG1vdmllcyksICIgQmV3ZXJ0dW5nZW4iKSwNCiAgICB4ID0gIkt1bmRlbmJld2VydHVuZ2VuIiwgDQogICAgeSA9ICJBbnphaGwiLA0KICAgIGZpbGwgPSBlbGVtZW50X2JsYW5rKCkNCiAgKSArDQogIHRoZW1lX2NsYXNzaWMoKSArDQogIHRoZW1lKA0KICAgIHRleHQgPSBlbGVtZW50X3RleHQoc2l6ZSA9IDEyKQ0KICApDQpgYGANCkluIGRpZXNlciBHcmFmaWsgaXN0IGRpZSBWZXJ0ZWlsdW5nIGRlciBiZXdlcnR1bmdlbiB6dSBzZWhlbi4gRGllIEJld2VydHVuZ2VuIDQgdW5kIDUgd2lyZGVuIGtsYXIgYW0gaMOkdWZpZ3N0ZW4gdmVyZ2ViZW4sIHdvYmVpIDEgdW5kIDIgZWhlciBzZWx0ZW4gYmV3ZXJ0ZXQgd2VyZGVuLg0KDQpgYGB7cn0NCiMgZ2V0IHJhdGluZyBjb3VudCBwZXIgdXNlciwgYWRkIGFzIGNvbHVtbiBmb3IgZnVydGhlciBwcm9jZXNzaW5nDQpjb3VudHMgPC0gbW92aWVzICU+JSBncm91cF9ieSh1c2VyKSAlPiUgY291bnQoKQ0KbW92aWVzIDwtIG1lcmdlKG1vdmllcywgY291bnRzLCBieT0idXNlciIpDQptb3ZpZXNfd2lkZXIgPC0gbWVyZ2UobW92aWVzX3dpZGVyLCBjb3VudHMsIGJ5PSJ1c2VyIikNCg0KIyBhdm9pZCB1c2VycyB3aXRoIGFsbW9zdCBubyByYXRpbmdzLCB1c2UgbWVkaWFuIGFzIHRocmVzaG9sZA0KbWVkaWFuX2NvdW50IDwtIG1lZGlhbihjb3VudHMkbikNCnByaW50KG1lZGlhbl9jb3VudCkNCg0KIyBnZXQgc2FtcGxlDQpzZXQuc2VlZCg2MjMpDQptb3ZpZXNfc2FtcGxlIDwtIG1vdmllc193aWRlciAlPiUgZmlsdGVyKG4gPiBtZWRpYW5fY291bnQpICU+JSBzYW1wbGVfbig1KQ0KDQojIGNyZWF0ZSBsb25nIHRhYmxlDQptb3ZpZXNfc2FtcGxlX2xvbmcgPC0gZmlsdGVyKG1vdmllcywgdXNlciAlaW4lIG1vdmllc19zYW1wbGUkdXNlcikNCg0KIyBkcm9wIGl0ZW0gbmFtZXMsIA0KbW92aWVzX3NhbXBsZV9sb25nIDwtIHN1YnNldChtb3ZpZXNfc2FtcGxlX2xvbmcsIHNlbGVjdCA9IC1jKGl0ZW0pKQ0KDQpkZjJiIDwtIGdlbnJlcyU+JQ0KICBncm91cF9ieShnZW5yZXMpDQogIA0KbW92aWVzX3NhbXBsZV9sb25nX2dyb3VwZWQgPC0gbW92aWVzX3NhbXBsZV9sb25nICU+JSBncm91cF9ieSh1c2VyLCByYXRpbmcpICU+JSBzdW1tYXJpc2UocmF0aW5nX2RlbnMgPSBsZW5ndGgodXNlcikgLyBmaXJzdChuKSwgdXNlciA9IGZpcnN0KHVzZXIpLCBuPWZpcnN0KG4pLCByYXRpbmcgPSBmaXJzdChyYXRpbmcpKQ0KICANCmdncGxvdChnZW5yZXMsIGFlcyh4ID0gcmF0aW5nLCBmaWxsID0gZ2VucmVzKSkgKw0KICBnZW9tX2JhcihhbHBoYSA9IDEsIGJpbnMgPSAxMCkgKw0KICBmYWNldF93cmFwKH5nZW5yZXMpKw0KICBzY2FsZV95X2NvbnRpbnVvdXMoZXhwYW5kID0gYygwLDApKSArDQogIHNjYWxlX3hfY29udGludW91cyhleHBhbmQgPSBjKDAsMCkpICsNCiAgbGFicygNCiAgICB0aXRsZSA9ICJWZXJ0ZWlsdW5nIEt1bmRlbnJhdGluZ3MgbmFjaCBHZW5yZXMiLA0KICAgIHN1YnRpdGxlID0gcGFzdGUoIk4gPSAiLCBucm93KG1vdmllcyksICIgQmV3ZXJ0dW5nZW4iKSwNCiAgICB4ID0gIkR1cmNoc2Nobml0dGxpY2hlIEJld2VydHVuZyIsIA0KICAgIHkgPSAiQW56YWhsIiwNCiAgICBmaWxsID0gZWxlbWVudF9ibGFuaygpDQogICkgKw0KICB0aGVtZSgNCiAgICB0ZXh0ID0gZWxlbWVudF90ZXh0KHNpemUgPSAxMiksDQogICAgbGVnZW5kLnBvc2l0aW9uID0gJ25vbmUnDQogICkNCmBgYA0KSGllciBpc3QgenUgc2VoZW4sIGRhc3MgZGFzIEdlbnJlcyBEcmFtYSBhbSBtZWlzdGVuIGJld2VydGV0IHd1cmRlLCB3b2JlaSBEb2t1bWVudGF0aW9uZW4gYW0gd2VuaWdzdGVuIEJld2VydHVuZ2VuIGVyaGFsdGVuIGhhYmVuLiBEaWUgQmV3ZXJ0dW5nZW4gcHJvIEdlbnJlcyB2ZXJ0ZWlsZW4gc2ljaCBqZXdlaWxzIHNlaHIgw6RobmxpY2guIERpZSBWZXJ0ZWlsdW5nZW4gZGVyIGVpbnplbG5lbiBHZW5yZXMgc2luZCBlYmVuZmFsbHMgw6RobmxpY2ggdmVydGVpbHQgd2llIGRpZSBiZXdlcnR1bmdlbiBnZXNhbXRoYWZ0Lg0KDQoqKioNCiMjIyMgMy5XaWUgdmVydGVpbGVuIHNpY2ggZGllIG1pdHRsZXJlbiBLdW5kZW5yYXRpbmdzIHBybyBGaWxtPw0KYGBge3J9DQpkZjMgPC0gbW92aWVzICU+JSANCiAgZ3JvdXBfYnkoaXRlbSkgJT4lICANCiAgc3VtbWFyaXplKA0KICAgIG1lYW5fcmF0aW5nID0gbWVhbihyYXRpbmcpLA0KICAgIHJhdGluZ3MgPSBuKCkNCiAgKSAlPiUgDQogIG11dGF0ZSgNCiAgICBtb3JlX3RoYW5fNTAgPSBpZmVsc2UocmF0aW5ncyA+PSA1MCwgJ2IpIG1laHIgYWxzIDUwIEJld2VydHVuZ2VuJywgJ2EpIHdlbmlnZXIgYWxzIDUwIEJld2VydHVnZW4nKQ0KICApDQoNCmdncGxvdChkZjMsIGFlcyh4ID0gbWVhbl9yYXRpbmcpKSArDQogIGdlb21fZGVuc2l0eShhbHBoYSA9IDEsIGZpbGwgPSAnc3RlZWxibHVlJywgYncgPSAwLjA4KSArDQogIHNjYWxlX3lfY29udGludW91cyhleHBhbmQgPSBjKDAsMCkpICsNCiAgc2NhbGVfeF9jb250aW51b3VzKGV4cGFuZCA9IGMoMCwwKSkgKw0KICBsYWJzKA0KICAgIHRpdGxlID0gIlZlcnRlaWx1bmcgbWl0dGxlcmUgS3VuZGVucmF0aW5ncyBwcm8gRmlsbSIsDQogICAgc3VidGl0bGUgPSBwYXN0ZSgiTiA9ICIsIG5yb3coZGYzKSwgIiBGaWxtZSIpLA0KICAgIHggPSAiRHVyY2hzY2huaXR0bGljaGUgQmV3ZXJ0dW5nIiwgDQogICAgeSA9ICJEaWNodGUiDQogICkgKw0KICB0aGVtZV9jbGFzc2ljKCkgKw0KICB0aGVtZSh0ZXh0ID0gZWxlbWVudF90ZXh0KHNpemUgPSAxMikNCiAgKQ0KYGBgDQpJbiBkaWVzZXIgR3JhZmlrIGlzdCBkaWUgZHVyY2hzY2huaXR0bGljaGUgQmV3ZXJ0dW5nIHBybyBGaWxtIHp1IHNlaGVuLCB3b2JlaSBhdWNoIGhpZXIgenUgc2VoZW4gaXN0ICxkYXNzIGRpZSBkaWUgbWVpc3RlbiBGaWxtZSBlaW5lIER1cmNoc2Nobml0dGxpY2hlIEJld2VydHVuZyB2b24gY2EuIDMgLSAzLjUgaGFiZW4uDQoNCmBgYHtyfQ0KZ2dwbG90KGRmMywgYWVzKHggPSBtZWFuX3JhdGluZywgZmlsbCA9IG1vcmVfdGhhbl81MCkpICsNCiAgZ2VvbV9kZW5zaXR5KGFscGhhID0gMC41LCBidyA9IDAuMDgpICsNCiAgc2NhbGVfeV9jb250aW51b3VzKGV4cGFuZCA9IGMoMCwwKSkgKw0KICBzY2FsZV94X2NvbnRpbnVvdXMoZXhwYW5kID0gYygwLDApKSArDQogIGxhYnMoDQogICAgdGl0bGUgPSAiVmVydGVpbHVuZyBtaXR0bGVyZSBLdW5kZW5yYXRpbmdzIHBybyBGaWxtIiwNCiAgICBzdWJ0aXRsZSA9ICJOID0gMTY2NCBGaWxtZSIsDQogICAgeCA9ICJEdXJjaHNjaG5pdHRsaWNoZSBCZXdlcnR1bmciLCANCiAgICB5ID0gIkRpY2h0ZSIsDQogICAgZmlsbCA9IGVsZW1lbnRfYmxhbmsoKQ0KICApICsNCiAgdGhlbWVfY2xhc3NpYygpICsNCiAgdGhlbWUoDQogICAgdGV4dCA9IGVsZW1lbnRfdGV4dChzaXplID0gMTIpLA0KICAgIGxlZ2VuZC5wb3NpdGlvbiA9ICdib3R0b20nDQogICkNCmBgYA0KRsO8ciBkaWVzZSBHcmFmaWsgd3VyZGVuIGRpZSBGaWxtZSBpbiB6d2VpIGdydXBwZW4gdW50ZXJ0ZWlsdDogRmlsbWUgZGllIHdlbmlnZXIgYWxzIDUwIGJld2VydHVuZ2VuIGVyaGFsdGVuIGhhYmVuLCB1bmQgRmlsbWUgd2VsY2hlIG1laHIgYWxzIDUwIEJld2VydHVuZ2VuIGVyaGFsdGVuIGhhYmVuLiBJbiBkZXIgR3JhZmlrIGlzdCBpbWVybm9jaCBkaWUgZHVyY2hzY2huaXR0bGljaGUgQmV3ZXJ0dW5nIGRpZXNlciBGaWxtZSB6dSBzZWhlbiB3b2JlaSBkZXV0bGljaCBlcmthbm50IHdlcmRlbiBrYW5uLCBkYXNzIGZpbG1lIHdlbGNoZSB3ZW5pZ2VyIGJld2VydHVuZ2VuIGVyaGFsdGVuIGhhYmVuLCB0ZW5kZW56aWVsbCBhdWNoIHNjaGxlY2h0ZXIgYmV3ZXJ0ZXQgd3VyZGVuLg0KDQoqKioNCiMjIyMgNC5XaWUgc3Rhcmsgc3RyZXVlbiBkaWUgUmF0aW5ncyB2b24gaW5kaXZpZHVlbGxlbiBLdW5kZW4/DQpgYGB7cn0NCiMgTnVtYmVyIG9mIHJhdGluZ3MgcGVyIHVzZXIgcGVyIHJhdGluZyB2YWx1ZQ0KbW92aWVzX3NhbXBsZV9sb25nX2dyb3VwZWQgPC0gbW92aWVzX3NhbXBsZV9sb25nICU+JSBncm91cF9ieSh1c2VyLCByYXRpbmcpICU+JSBzdW1tYXJpc2UocmF0aW5nX2RlbnMgPSBsZW5ndGgodXNlcikgLyBmaXJzdChuKSwgdXNlciA9IGZpcnN0KHVzZXIpLCBuPWZpcnN0KG4pLCByYXRpbmcgPSBmaXJzdChyYXRpbmcpKQ0KbW92aWVzX3NhbXBsZV9sb25nX2dyb3VwZWQNCm1vdmllc19zYW1wbGVfbG9uZw0KDQpnZ3Bsb3QobW92aWVzX3NhbXBsZV9sb25nX2dyb3VwZWQsIGFlcyh4PXJhdGluZywgeSA9IHJhdGluZ19kZW5zLCBmaWxsPXVzZXIpKSArIA0KICBnZW9tX2NvbChwb3NpdGlvbj1wb3NpdGlvbl9kb2RnZSgpKSArDQogIHNjYWxlX3lfY29udGludW91cyhleHBhbmQgPSBjKDAsMCkpICsNCiAgc2NhbGVfeF9jb250aW51b3VzKGV4cGFuZCA9IGMoMCwwKSkgKw0KICBsYWJzKA0KICAgIHRpdGxlID0gIlN0cmV1dW5nIEt1bmRlbmJld2VydHVuZ2VuIGbDvHIgenVmw6RsbGlnIGdld8OkaGx0ZSBLdW5kZW4iLA0KICAgIHN1YnRpdGxlID0gIk4gPSA1IEt1bmRlbiIsDQogICAgeCA9ICJVc2VyIEJld2VydHVuZyAoMS01KSIsIA0KICAgIHkgPSAiQXVzcHLDpGd1bmcgUmF0aW5nIiwNCiAgICBmaWxsID0gZWxlbWVudF9ibGFuaygpDQogICkgKw0KICBzY2FsZV9maWxsX21hbnVhbCgibGVnZW5kIiwgdmFsdWVzID0gYygiY3lhbjMiLCAiY3lhbjQiLCAiZGFya29saXZlZ3JlZW4zIiwgImRhcmtvbGl2ZWdyZWVuIiwgImNvcmFsNCIpDQogICAgICAgICAgICAgICAgICAgICkrDQogIHRoZW1lX2NsYXNzaWMoKSArIA0KICB0aGVtZSgNCiAgICB0ZXh0ID0gZWxlbWVudF90ZXh0KHNpemUgPSAxMiksDQogICAgbGVnZW5kLnBvc2l0aW9uID0gJ2JvdHRvbScNCiAgKQ0KDQpgYGANCkluIGRpZXNlciBHcmFmaWsgc2VoZW4gd2lyLCB3aWUgc2ljaCBkaWUgQmV3ZXJ0dW5nZW4gZWluemVsbmVyIEt1bmRlbiB2ZXJ0ZWlsZW4uIEF1ZmZhbGxlbmQgaXN0IGdlbmVyZWxsLCBkYXNzIGRpZSBCZXdlcnR1bmdlbiAxIHVuZCAyIHdlbmlnZXIgb2Z0IGFiZ2VnZWJlbiB3dXJkZSBhbHMgMyB1bmQgNC4gDQpCZWkgZGVyIFZlcnRlaWx1bmcgZGVyIHJhdGluZ3Mgc2luZCB2b24gVXNlciB6dSBVc2VyIFVudGVyc2NoaWVkZSBmZXN0c3RlbGxiYXIuIFVzZXIgMjQgYmV3ZXJ0ZXQgYmVpc3BpZWxzd2Vpc2UgdmllbCBiZXNzZXIgYWxzIFVzZXIgNjM5LiBEaWVzIGvDtm5udGUgYmVkZXV0ZW4sIGRhc3MgVXNlciAyNCBudXIgRmlsbWUgYmV3ZXJ0ZXQgb2RlciBzY2hhdXQgZGllIGVyL3NpZSBtYWcsIG9kZXIgZ3J1bmRzw6R0emxpY2ggaMO2aGVyZSBCZXdlcnR1bmdlbiBhYmdpYnQuIExlaWRlciBzZWhlbiB3aXIgaGllciB3ZW5pZ2VyIGd1dCwgd2VsY2hlIFRlbmRlbnplbiBkaWUgU3RyZXV1bmcgZGVyIFJhdGluZyBhbGxlciBVc2VyIGF1ZndlaXNlbi4NCg0KYGBge3J9DQptb3ZpZXNfc3BhbiA8LSBtb3ZpZXMgJT4lIGdyb3VwX2J5KHVzZXIpICU+JSANCiAgc3VtbWFyaXplKG1lYW4gPSBtZWFuKHJhdGluZyksIG1pbiA9IG1pbihyYXRpbmcpLCBtYXggPSBtYXgocmF0aW5nKSwgc3BhbiA9IChtYXgocmF0aW5nKSAtIG1pbihyYXRpbmcpKSkNCg0KbW92aWVzX3NwYW4NCg0Kc2V0LnNlZWQoMTIzKQ0KDQpnZ3Bsb3Qoc2FtcGxlX24obW92aWVzX3NwYW4sIDIwKSwgYWVzKHg9dXNlcikpICsNCiAgZ2VvbV9wb2ludChjb2xvdXI9ImJsYWNrIiwgYWVzKHk9bWVhbiksIHNoYXBlPTIxKSArDQogIGdlb21fZXJyb3JiYXIoYWVzKHltaW49bWluLCB5bWF4PW1heCkpICsNCiAgbGFicygNCiAgICB0aXRsZSA9ICJTcGFubndlaXRlIEt1bmRlbnJhdGluZ3MgIiwNCiAgICBzdWJ0aXRsZSA9ICJOID0gMjAgS3VuZGVuIiwNCiAgICB4ID0gIlVzZXIgSUQiLCANCiAgICB5ID0gIlJhdGluZyBSYW5nZSINCiAgKSsNCiAgICB0aGVtZV9jbGFzc2ljKCkgKyANCiAgdGhlbWUoDQogICAgdGV4dCA9IGVsZW1lbnRfdGV4dChzaXplID0gMTIpLA0KICAgIGxlZ2VuZC5wb3NpdGlvbiA9ICdib3R0b20nDQogICkNCg0KDQpnZ3Bsb3QobW92aWVzX3NwYW4sIGFlcyh4PXVzZXIpKSArDQogIGdlb21fYmFyKGNvbG91cj0iYmxhY2siLCBhZXMoc3BhbikpICsNCiAgbGFicygNCiAgICB0aXRsZSA9ICJTcGFubndlaXRlIEt1bmRlbnJhdGluZ3MiLA0KICAgIHN1YnRpdGxlID0gIiIsDQogICAgeCA9ICJTcGFubndlaXRlIiwgDQogICAgeSA9ICJBbnphaGwgVXNlciINCiAgKSsNCiAgICB0aGVtZV9jbGFzc2ljKCkgKyANCiAgdGhlbWUoDQogICAgdGV4dCA9IGVsZW1lbnRfdGV4dChzaXplID0gMTIpLA0KICAgIGxlZ2VuZC5wb3NpdGlvbiA9ICdib3R0b20nDQogICkNCiAgDQpgYGANCjBJbiBkaWVzZW4gR3JhZmlrZW4gc2VoZW4gd2lyIGRldGFpbGxpZXJ0ZXJlIEluZm9ybWF0aW9uZW4gw7xiZXIgZGllIFNwYW5ud2VpdGUgdW5kIGRlbiBNaXR0ZWxwdW5rdC4gSW4gZGVyIGVyc3RlbiDDnGJlcnNpY2h0IGlzdCBkaWUgU3Bhbm53ZWl0ZSB1bmQgZGVyIE1pdHRlbHB1bmt0IGVpbnplbG5lciBLdW5kZW4gZGFyZ2VzdGVsbHQuIEVzIGbDpGxsdCBhdWYsIGRhc3MgdHJvdHogZGVzIHRlaWx3ZWlzZSByZWxhdGl2IGhvaGVtIE1pdHRlbHdlcnQgYWxsZSBSYXRpbmdzIHZvbiAxLTUgYWJnZWdlYmVuIHd1cmRlbi4gRWluIHJhdGluZyB2b24gNSB3dXJkZSBzb3p1c2FnZW4gaW1tZXIgYWJnZWdlYmVuLCAxIG5pY2h0IGltbWVyLg0KSW4gZGVyIHp3ZWl0ZW4gw5xiZXJzaWNodCBpc3QgZGllIFNwYW5ud2VpdGUgYWxsZXIgS3VuZGVuIGRhcmdlc3RlbGx0LiBIaWVyIHdpcmQgc2ljaHRiYXIsIGRhc3MgZGllIG1laXN0ZW4gS3VuZGVuIEJld2VydHVuZ2VuIHZvbiAxLTUgYWJnZWdlYmVuIGhhYmVuIChTcGFubndlaXRlPTQpLCB1bmQgbnVyIHdlaW5pZ2Ugc2VociBob21vZ2VuIGJld2VydGV0IGhhYmVuIChTcGFubndlaXRlID0gMS0yKS4gRWluZSBrbGVpbmUgU3Bhbm53ZWl0ZSBrYW5uIGhpZXIgYXVjaCBhdWZnZXRyZXRlbiBzZWluLCBkYSBkaWVzZSBVc2VyIHNlaHIgd2VuaWdlIEJld2VydHVuZ2VuIGFiZ2VnZWJlbiBoYWJlbi4NCg0KKioqDQojIyMjIDUuV2VsY2hlbiBFaW5mbHVzcyBoYXQgZGllIE5vcm1pZXJ1bmcgZGVyIFJhdGluZ3MgcHJvIEt1bmRlIGF1ZiBkZXJlbiBWZXJ0ZWlsdW5nPw0KYGBge3J9DQpoaXN0KGdldFJhdGluZ3MoTW92aWVMZW5zZSksIA0KICAgICBicmVha3M9MTUsDQogICAgIG1haW4gPSAiVmVydGVpbHVuZyBkZXIgQmV3ZXJ0dW5nZW4iKQ0KI2hpc3QoZ2V0UmF0aW5ncyhNb3ZpZUxlbnNlTm9ybSksIGJyZWFrcz00MCkNCmBgYA0KRGllIFJhdGluZ3Mgc2luZCBudW4gdW5nZWbDpGhyIE5vcm1hbHZlcnRlaWx0IG1pdCBlaW5lbSBEdXJjaHNjaG5pdHRzcmF0aW5nIHZvbiAwIHVuZCBlaW5lciBTdGFuZGFyZGFid2VpY2h1bmcgdm9uIDEuIA0KRXJrZW5uYmFyIGlzdCwgZGFzcyBkaWUgVmVydGVpbHVuZyByZWNodHNzdGVpbCB1bmQgbGlua3NzY2hpZWYgaXN0LCBhbHNvIG1laHJoZWl0bGljaCBwb3NpdGl2ZSBCZXdlcnR1bmdlbiBhYmdlZ2ViZW4gd3VyZGVuLiANCkR1cmNoIGRpZSBOb3JtaWVydW5nIGRlciBEYXRlbiB3ZXJkZW4gZGllIFJhdGluZ3MgamVkZXMgVXNlcnMgYXVmIGRpZXNlbGJlIFZlcnRlaWx1bmcgZ2VzdGF1Y2h0LCB3b2R1cmNoIG1hbiBkaWUgVmVydGVpbHVuZyBhbGxlciBEYXRlbiBhbmFseXNpZXJlbiBrYW5uLiBEYWR1cmNoIGhhdCBtYW4gYmVpc3BpZWxzd2Vpc2UgZGllIE3DtmdsaWNoa2VpdCBkaWUgZHVyY2hzY2huaXR0bGljaGUgQmV3ZXJ0dW5nc3RlbmRlbnogaGVyYXVzenVmaW5kZW4uIA0KDQoqKioNCiMjIyMgNi5XZWxjaGUgc3RydWt0dXJlbGxlbiBDaGFyYWt0ZXJpc3Rpa2EgKHouQi4gU3BhcnNpdHkpIHVuZCBBdWZmw6RsbGlna2VpdGVuIHplaWd0IGRpZSBVc2VyIEl0ZW0gTWF0cml4Pw0KYGBge3J9DQppbWFnZShNb3ZpZUxlbnNlLCBtYWluID0gIlJhdyBSYXRpbmdzIikNCg0KTW92aWVMZW5zZU5vcm0gPC0gbm9ybWFsaXplKE1vdmllTGVuc2UsIG1ldGhvZD0iWi1zY29yZSIpDQppbWFnZShNb3ZpZUxlbnNlTm9ybSwgbWFpbiA9ICJOb3JtYWxpemVkIFJhdGluZ3MiKQ0KYGBgDQpVc2VycyBtaXQgdGllZmVuIElEJ3MgdW5kIEZpbG1lIG1pdCBob2hlbiBJRCdzIHdlaXNlbiB3ZW5pZ2VyIHJhdGluZ3MgYXVmLiBGaWxtZSBtaXQgdGllZmVyIElEIGplZG9jaCBzZWhyIHZpZWxlLg0KQXVmZmFsbGVuZCBpc3QsIGRhc3MgZXMgZWluaWdlIHdlbmlnZSBVc2VyIGdpYnQsIGRpZSBmYXN0IGFsbGUgRmlsbWUgYmV3ZXJ0ZXQgaGFiZW4gKGVya2VubmJhciBkdXJjaCBkaWUgaG9yaXpvbnRhbGVuIHNjaGFyemVuIFN0cmljaGUpLiBEaWVzIHNjaGVpbmVuIHNlaHIgYWt0aXZlIEJld2VydGVyIHp1IHNlaW4uDQpWaWVsZSBVc2VycyBoYWJlbiBqZWRvY2ggbnVyIGVpbmVuIGtsZWluZW4gVGVpbCBkZXIgRmlsbWUgYmV3ZXJ0ZXQuDQpCZWkgZGVuIEZpbG1lbiBpc3QgZWluZSDDpGhubGljaGUgVGVuZGVueiB3YWhyenVuZWhtZW4sIGplZG9jaCBzaW5kIGRpZSB2ZXJ0aWthbGVuIFN0cmljaGUgYnJlaXRlci4gTcO2Z2xpY2hlcndlaXNlIHNpbmQgZG9ydCBlaW5pZ2UgYmVsaWVidGUgRmlsbWUgenVzYW1tZW5nZWZhc3N0Lg0KDQoqKioNCiMjIERhdGVucmVkdWt0aW9uDQpgYGB7cn0NCnJhdGluZ01hdHJpeCA8LSBkYXRhX3JlZHVjdGlvbl9kZW5zZShNb3ZpZUxlbnNlKQ0KcmF0aW5nTWF0cml4DQpgYGANCg0KYGBge3J9DQpnZXRfc3BhcnNpdHkgPC0gZnVuY3Rpb24oTWF0cml4KSB7DQogIHJvdW5kKCggMSAtIChucmF0aW5ncyhNYXRyaXgpIC8gKGRpbShNYXRyaXgpWzFdICogZGltKE1hdHJpeClbMl0pKSkgKiAxMDAsMikNCn0NCg0Kc2hvd19zcGFyc2l0eSA8LSBmdW5jdGlvbihNYXRyaXgsIE5hbWUpIHsNCg0KICBNZWFzdXJlbWVudCA8LSBsaXN0KCdNYXRyaXgnLCdEaW1lbnNpb24nLCAnU3BhcnNpdHknLCAnRGVuc2l0eScpDQogIFZhbHVlIDwtIGxpc3QoTmFtZSwgcGFzdGUoJygnLHRvU3RyaW5nKGRpbShNYXRyaXgpKSwgJyknKSxwYXN0ZShnZXRfc3BhcnNpdHkoTWF0cml4KSwgJyUnICksIHBhc3RlKDEwMCAtIGdldF9zcGFyc2l0eShNYXRyaXgpLCAnJScgKSkNCiAgZGYgPC0gY2JpbmQoTWVhc3VyZW1lbnQsVmFsdWUpDQogIGhlYWQoZGYpDQp9DQoNCnNob3dfc3BhcnNpdHlfY2hhbmdlIDwtIGZ1bmN0aW9uKG9sZE1hdHJpeCwgbmV3TWF0cml4KSB7DQogIHByaW50KGxpc3Qoc2hvd19zcGFyc2l0eShvbGRNYXRyaXgsICdPbGQgTWF0cml4JyksIHNob3dfc3BhcnNpdHkobmV3TWF0cml4LCAnTmV3IE1hdHJpeCcpKSkNCiAgDQogIA0KfQ0KDQpzaG93X3NwYXJzaXR5X2NoYW5nZShNb3ZpZUxlbnNlLCByYXRpbmdNYXRyaXgpDQpgYGANCg0KYGBge3J9DQpvbGRfbWF0cml4IDwtIGFzKE1vdmllTGVuc2UsICJkYXRhLmZyYW1lIikgJT4lIA0KICBncm91cF9ieShpdGVtKSAlPiUgIA0KICBzdW1tYXJpemUoDQogICAgbWVhbl9yYXRpbmcgPSBtZWFuKHJhdGluZyksDQogICAgcmF0aW5ncyA9IG4oKQ0KICApICU+JSANCiAgbXV0YXRlKA0KICAgIG1hdHJpeCA9ICdhKSBhbHRlIE1hdHJpeCcNCiAgKQ0KDQpuZXdfbWF0cml4IDwtIGFzKHJhdGluZ01hdHJpeCwgImRhdGEuZnJhbWUiKSAlPiUgDQogIGdyb3VwX2J5KGl0ZW0pICU+JSAgDQogIHN1bW1hcml6ZSgNCiAgICBtZWFuX3JhdGluZyA9IG1lYW4ocmF0aW5nKSwNCiAgICByYXRpbmdzID0gbigpDQogICkgJT4lIA0KICBtdXRhdGUoDQogICAgbWF0cml4ID0gJ2IpIG5ldWUgTWF0cml4Jw0KICApDQoNCmNvbXBhcmlzb24gPC0gYmluZF9yb3dzKG9sZF9tYXRyaXgsIG5ld19tYXRyaXgpDQoNCmdncGxvdChjb21wYXJpc29uLCBhZXMoeCA9IG1lYW5fcmF0aW5nLCBmaWxsID0gbWF0cml4KSkgKw0KICBnZW9tX2RlbnNpdHkoYWxwaGEgPSAwLjUsIGJ3ID0gMC4wOCkgKw0KICBzY2FsZV95X2NvbnRpbnVvdXMoZXhwYW5kID0gYygwLDApKSArDQogIHNjYWxlX3hfY29udGludW91cyhleHBhbmQgPSBjKDAsMCkpICsNCiAgbGFicygNCiAgICB0aXRsZSA9ICJWZXJ0ZWlsdW5nIG1pdHRsZXJlIEt1bmRlbnJhdGluZ3MgcHJvIEZpbG0iLA0KICAgIHN1YnRpdGxlID0gIk4gPSAxNjY0IEZpbG1lIiwNCiAgICB4ID0gIkR1cmNoc2Nobml0dGxpY2hlIEJld2VydHVuZyIsIA0KICAgIHkgPSAiRGljaHRlIiwNCiAgICBmaWxsID0gZWxlbWVudF9ibGFuaygpDQogICkgKw0KICB0aGVtZV9jbGFzc2ljKCkgKw0KICB0aGVtZSgNCiAgICB0ZXh0ID0gZWxlbWVudF90ZXh0KHNpemUgPSAxMiksDQogICAgbGVnZW5kLnBvc2l0aW9uID0gYyguOTAsIC45NSkNCiAgKQ0KYGBgDQoNCmBgYHtyfQ0KaW1hZ2UocmF0aW5nTWF0cml4LCBtYWluID0gIlJhdyBSYXRpbmdzIikNCmBgYA0KDQoqKioNCiMjIEFuYWx5c2Ugw4RobmxpY2hrZWl0c21hdHJpeA0KIyMjIyAxLiBaZXJsZWdlIGRlbiByZWR1emllcnRlbiBNb3ZpZUxlbnNlIERhdGVuc2F0eiBpbiBlaW4gZGlzanVua3RlcyBUcmFpbmluZ3MtIHVuZCBUZXN0ZGF0ZW5zZXQgaW0gVmVyaMOkbHRuaXMgNDoxDQpgYGB7cn0NCiNzcGxpdCA8LSByb3dDb3VudChyYXRpbmdNYXRyaXgpICogMC43NQ0KIyB0cmFpbiA8LSByYXRpbmdNYXRyaXhbMTozMDBdDQojIHRlc3QgPC0gcmF0aW5nTWF0cml4WzMwMTo0MDBdDQoNCiMgdHJhaW4tdGVzdCBzcGxpdCANCnNldC5zZWVkKDQyKQ0KZGF0YSA8LSBhcyhyYXRpbmdNYXRyaXgsICJkYXRhLmZyYW1lIikNCmRmIDwtIGRhdGEgJT4lIGdyb3VwX2J5KHVzZXIpICU+JSBzdW1tYXJpemUobWVhbl9yYXRpbmcgPSBtZWFuKHJhdGluZykpDQoNCmRmIDwtIHNhbXBsZV9mcmFjKGRmLCBzaXplID0gMC44LCByZXBsYWNlID0gRkFMU0UpDQpkZl90cmFpbiA8LSBzZW1pX2pvaW4oZGF0YSxkZixieT0ndXNlcicpDQpkZl90ZXN0IDwtIGFudGlfam9pbihkYXRhLGRmX3RyYWluLGJ5PSd1c2VyJykNCnRyYWluIDwtIGFzKGRmX3RyYWluLCAicmVhbFJhdGluZ01hdHJpeCIpDQp0ZXN0IDwtIGFzKGRmX3Rlc3QsICdyZWFsUmF0aW5nTWF0cml4JykNCg0KZGltKHRyYWluKQ0KZGltKHRlc3QpDQoNCmBgYA0KDQoqKioNCiMjIyMgMi4gVHJhaW5pZXJlIGVpbiBJQkNGIE1vZGVsbCBtaXQgMzAgTmFjaGJhcm4gdW5kIENvc2luZSBTaW1pbGFyaXR5DQpgYGB7cn0NCg0KcmVjIDwtIFJlY29tbWVuZGVyKHRyYWluLCBtZXRob2QgPSAiSUJDRiIsIHBhcmFtPWxpc3QobWV0aG9kPSJDb3NpbmUiLCBrPTMwLCBub3JtYWxpemUgPSBOVUxMLCBuYV9hc196ZXJvID0gVFJVRSkpICNub3JtYWxpemUgPSAnY2VudGVyJw0KcmVjDQoNCiMgcHJlZGljdCB0b3AgMTAgbW92aWVzIGZvciAxMDAgdXNlcnMNCnByZSA8LSBwcmVkaWN0KHJlYywgdGVzdCwgbiA9IDEwKQ0KcHJlDQoNCnJlY29fbGlzdCA8LSBhcyhwcmUsICJsaXN0IikNCg0KIyB0b3AgMTAgcmVjb21tZW5kYXRpb25zIGZvciB0aGUgMTN0aCB1c2VyIGluIHJlY29fbGlzdA0KcmVjb19saXN0WzEzXQ0KDQojaW1hZ2UoYXMocHJlLCAibWF0cml4IikpDQoNCmBgYA0KKioqDQojIyMjIDMuIEJlc3RpbW1lIGRpZSBWZXJ0ZWlsdW5nIGRlciBGaWxtZSwgd2VsY2hlIGJlaSBJQkNGIGbDvHIgcGFhcndlaXNlIMOEaG5saWNoa2VpdHN2ZXJnbGVpY2hlIHZlcndlbmRldCB3ZXJkZW4NCmBgYHtyfQ0KbW9kZWwgPC0gZ2V0TW9kZWwocmVjKQ0KY29sU3VtIDwtIGNvbFN1bXMobW9kZWwkc2ltID4gMCkNCg0KZGYgPC0gYXMuZGF0YS5mcmFtZShjb2xTdW0pDQoNCiMgYWRkIGluZGV4IGNvbHVtbg0KZGYgPC0gY2JpbmQoaXRlbSA9IHJvd25hbWVzKGRmKSwgZGYpDQpyb3duYW1lcyhkZikgPC0gMTpucm93KGRmKQ0KDQpnZ3Bsb3QoZGYsIGFlcyh4ID0gY29sU3VtKSkgKw0KICBnZW9tX2RlbnNpdHkoYWxwaGEgPSAxLCBmaWxsID0gJ3N0ZWVsYmx1ZScsIGJ3ID0gNCkgKw0KICBzY2FsZV95X2NvbnRpbnVvdXMoZXhwYW5kID0gYygwLDApKSArDQogIHNjYWxlX3hfY29udGludW91cyhleHBhbmQgPSBjKDAsMCkpICsNCiAgbGFicygNCiAgICB0aXRsZSA9ICJWZXJ0ZWlsdW5nIGRlciBBbnphaGwgw6RobmxpY2hlciBGaWxtZSIsDQogICAgIyBzdWJ0aXRsZSA9IHBhc3RlKCJOID0gIiwgbnJvdyhkZjMpLCAiIEZpbG1lIiksDQogICAgeCA9ICJIw6R1Zmlna2VpdCB6dSBkZXIgZGVyIEZpbG0gYWxzIE5hY2hiYXIgYXVmdGF1Y2h0IiwgDQogICAgeSA9ICJIw6R1Zmlna2VpdCINCiAgKSArDQogIHRoZW1lX2NsYXNzaWMoKSArDQogIHRoZW1lKHRleHQgPSBlbGVtZW50X3RleHQoc2l6ZSA9IDEyKQ0KICApDQpgYGANCg0KKioqDQojIyMjIDQuIEJlc3RpbW1lIGRpZSBGaWxtZSwgZGllIGFtIGjDpHVmaWdzdGVuIGluIGRlciBDb3NpbmUtw4RobmxpY2hrZWl0c21hdHJpeCBhdWZ0YXVjaGVuIHVuZCBhbmFseXNpZXJlIGRlcmVuIFZvcmtvbW1lbiB1bmQgUmF0aW5ncyBpbSByZWR1emllcnRlbiBEYXRlbnNhdHoNCmBgYHtyfQ0KZGYxIDwtIGRmICU+JSBhcnJhbmdlKGRlc2MoY29sU3VtKSkgJT4lIGhlYWQoMTApDQpkZjENCg0KZ2dwbG90KGRmMSwgYWVzKHggPSBjb2xTdW0sIHkgPSByZW9yZGVyKGl0ZW0sICtjb2xTdW0pKSkrDQogIGdlb21fY29sKGFscGhhID0gMSwgZmlsbCA9ICdzdGVlbGJsdWUnKSsNCiAgc2NhbGVfeV9kaXNjcmV0ZShleHBhbmQgPSBjKDAsMCkpICsNCiAgc2NhbGVfeF9jb250aW51b3VzKGV4cGFuZCA9IGMoMCwwKSkgKw0KICBnZW9tX3RleHQoYWVzKGxhYmVsPXJvdW5kKGNvbFN1bSwyKSksIGhqdXN0ID0gMS4zLCBjb2xvciA9ICd3aGl0ZScpICsNCiAgbGFicygNCiAgICB0aXRsZSA9ICJIw6R1Zmlnc3RlIEZpbG1lIGluIENvc2luZS3DhGhubGljaGtlaXRzbWF0cml4IiwNCiAgICB5ID0gZWxlbWVudF9ibGFuaygpLA0KICAgIHggPSAiQW56YWhsIEZpbG1lIGluIGRlcmVuIE5hY2hiYXJzY2hhZnQgZGVyIEZpbG0gaXN0Ig0KICApICsNCiAgdGhlbWVfY2xhc3NpYygpICsNCiAgdGhlbWUoYXhpcy50ZXh0LnggPSBlbGVtZW50X2JsYW5rKCksDQogICAgICAgIGF4aXMudGlja3MueCA9IGVsZW1lbnRfYmxhbmsoKSwNCiAgICAgICAgYXhpcy5saW5lLnggPSBlbGVtZW50X2JsYW5rKCksDQogICAgICAgIHRleHQgPSBlbGVtZW50X3RleHQoc2l6ZSA9IDEyKSAjIHRleHQgc2l6ZQ0KICApDQpgYGANCg0KYGBge3J9DQp0b3AxMCA8LSBhcy5saXN0KGRmMSkkaXRlbQ0KDQpkYXRhIDwtIGFzKHJhdGluZ01hdHJpeCwgImRhdGEuZnJhbWUiKQ0KZGF0YTEgPC0gZGF0YSAlPiUNCiAgZ3JvdXBfYnkoaXRlbSkgJT4lDQogIHN1bW1hcml6ZShtZWFuX3JhdGluZyA9IG1lYW4ocmF0aW5nKSkgJT4lDQogIGFycmFuZ2UoZGVzYyhtZWFuX3JhdGluZykpICU+JQ0KICBtdXRhdGUoY2F0ZWdvcnkgPSBpZmVsc2UoaXRlbSAlaW4lIHRvcDEwLCAnSMOkdWZpZ3N0ZSAxMCBGaWxtZScsICdSZXN0bGljaGUgRmlsbWUnKSkNCg0KZ2dwbG90KGRhdGExLCBhZXMoeCA9IG1lYW5fcmF0aW5nLCBmaWxsID0gY2F0ZWdvcnkpKSArDQogIGdlb21fZGVuc2l0eShhbHBoYSA9IDAuNSwgYncgPSAwLjA1KSArDQogIHNjYWxlX3lfY29udGludW91cyhleHBhbmQgPSBjKDAsMCkpICsNCiAgc2NhbGVfeF9jb250aW51b3VzKGV4cGFuZCA9IGMoMCwwKSkgKw0KICBsYWJzKA0KICAgIHRpdGxlID0gIlZlcnRlaWx1bmcgbWl0dGxlcmUgS3VuZGVucmF0aW5ncyBwcm8gRmlsbSIsDQogICAgeCA9ICJEdXJjaHNjaG5pdHRsaWNoZSBCZXdlcnR1bmciLA0KICAgIHkgPSAiRGljaHRlIiwNCiAgICBmaWxsID0gZWxlbWVudF9ibGFuaygpDQogICkgKw0KICB0aGVtZV9jbGFzc2ljKCkgKw0KICB0aGVtZSgNCiAgICB0ZXh0ID0gZWxlbWVudF90ZXh0KHNpemUgPSAxMiksDQogICAgbGVnZW5kLnBvc2l0aW9uID0gYyguMTQsIC45MykNCiAgKQ0KYGBgDQoqKioNCiMjIyMgSW1wbGVtZW50aWVydW5nIFRvcC1OIE1ldHJpa2VuDQpgYGB7cn0NCnNob3dfcHJlY2lzaW9uIDwtIGZ1bmN0aW9uKGxpc3RPZkRpZmZlcmVudE4sIHJhdGluZ01hdHJpeCwgdGhyZXNob2xkKSB7DQogIA0KICAjIG5vcm1hbGl6ZSB0aGUgcmF0aW5nIG1hdHJpeA0KICByYXRpbmdNYXRyaXggPC0gbm9ybWFsaXplKHJhdGluZ01hdHJpeCwgbWV0aG9kPSJaLXNjb3JlIiwgcm93PVRSVUUpDQogIA0KICAjIGNyZWF0ZSBhIHRyYWluaW5nIHNldCBhbmQgYSB0ZXN0IHNldCB3aXRoIHRydWUgcG9zaXRpdmVzIGZvciByZWNhbGwgYW5kIHByZWNpc2lvbg0KICBkYXRhIDwtIGFzKHJhdGluZ01hdHJpeCwgImRhdGEuZnJhbWUiKQ0KICByZWxldmFudCA8LSBkYXRhICU+JSBncm91cF9ieSh1c2VyKSAlPiUgc2FtcGxlX24oMzApDQogIHRydWVfcG9zaXRpdmVzIDwtIHJlbGV2YW50ICU+JSBmaWx0ZXIocmF0aW5nID49IHRocmVzaG9sZCkNCiAgZmFsc2VfcG9zaXRpdmVzIDwtIHJlbGV2YW50ICU+JSBmaWx0ZXIocmF0aW5nIDwgdGhyZXNob2xkKQ0KICANCiAgIyByZW1vdmUgdGVzdGluZyBvYnNlcnZhdGlvbnMgZnJvbSB0cmFpbmluZyBzZXQNCiAgdHJhaW4gPC0gYW50aV9qb2luKGRhdGEsIHJlbGV2YW50LGJ5PWMoJ3VzZXInLCdpdGVtJykpDQogIHRyYWluIDwtIGFzKHRyYWluLCAncmVhbFJhdGluZ01hdHJpeCcpDQogIA0KICAjIHRyYWluIG1vZGVsIGJhc2VkIG9uIHRyYWluaW5nIHNldA0KICByZWMgPC0gUmVjb21tZW5kZXIodHJhaW4sIG1ldGhvZCA9ICJJQkNGIiwgcGFyYW09bGlzdChtZXRob2Q9IkNvc2luZSIsIGs9MzAsIG5vcm1hbGl6ZSA9IE5VTEwsIG5hX2FzX3plcm8gPSBUUlVFKSkgI25vcm1hbGl6ZSA9ICdjZW50ZXInLCAnWi1zY29yZScNCiAgDQogIGZvciAoTiBpbiBsaXN0T2ZEaWZmZXJlbnROKSB7DQoNCiAgICAjIHByZWRpY3QgdG9wIE4gbW92aWVzDQogICAgcHJlIDwtIHByZWRpY3QocmVjLCB0cmFpbiwgbiA9IE4pDQogICAgcmVjb19saXN0IDwtIGFzKHByZSwgImxpc3QiKQ0KICAgIHJlY29tbWVuZGF0aW9ucyA8LSBhcy5kYXRhLmZyYW1lKHJlY29fbGlzdCkNCiAgICANCiAgICAjIGZpbmQgdHJ1ZSBwb3NpdGl2ZXMgYW5kIGZhbHNlIHBvc2l0aXZlcyBmb3IgYWxsIHVzZXJzIGFuZCBhZGQgdGhlbSB1cA0KICAgIHRydWVfdG90YWwgPC0gMA0KICAgIGZhbHNlX3RvdGFsIDwtIDANCiAgICBmb3IgKGkgaW4gYXMubGlzdCh1bmlxdWUodHJ1ZV9wb3NpdGl2ZXNbJ3VzZXInXSkpJHVzZXIpIHsNCiAgICAgIG91cl91c2VyIDwtIHBhc3RlKCdYJywgaSwgc2VwID0gJycpDQogICAgICByZWNvbW1lbmRhdGlvbnNbJ2l0ZW0nXSA8LSByZWNvbW1lbmRhdGlvbnNbb3VyX3VzZXJdDQoNCiAgICAgIHRydWVfdG90YWwgPC0gdHJ1ZV90b3RhbCArIG5yb3coaW5uZXJfam9pbihyZWNvbW1lbmRhdGlvbnNbJ2l0ZW0nXSwgdHJ1ZV9wb3NpdGl2ZXMgJT4lIGZpbHRlcih1c2VyID09IGFzLmludGVnZXIoaSkpLCBieSA9ICdpdGVtJykpDQogICAgICBmYWxzZV90b3RhbCA8LSBmYWxzZV90b3RhbCArIG5yb3coaW5uZXJfam9pbihyZWNvbW1lbmRhdGlvbnNbJ2l0ZW0nXSwgZmFsc2VfcG9zaXRpdmVzICU+JSBmaWx0ZXIodXNlciA9PSBhcy5pbnRlZ2VyKGkpKSwgYnkgPSAnaXRlbScpKQ0KICAgIH0NCiAgICANCiAgICAjIHByaW50IFN1bW1hcnkNCiAgICBwcmludChwYXN0ZSgnTiA9JywgTikpDQogICAgcHJpbnQocGFzdGUoJ051bWJlciBvZiBUcnVlIFBvc2l0aXZlczonLHRydWVfdG90YWwpKQ0KICAgIHByaW50KHBhc3RlKCdOdW1iZXIgb2YgRmFsc2UgUG9zaXRpdmVzOicsZmFsc2VfdG90YWwpKQ0KICAgIHByaW50KHBhc3RlKCdQcmVjaXNpb246Jyx0cnVlX3RvdGFsIC8gKHRydWVfdG90YWwgKyBmYWxzZV90b3RhbCkpKQ0KICAgIHByaW50KCcnKQ0KICB9DQp9DQoNCnNob3dfcHJlY2lzaW9uKGMoNSwxMCwxNSwyMCwyNSwzMCksIHJhdGluZ01hdHJpeCwgMCkNCmBgYA0KDQoqKioNCiMjIyMgQ2F0YWxvZyBjb3ZlcmFnZQ0KYGBge3J9DQpyZWMgPC0gUmVjb21tZW5kZXIodHJhaW4sIG1ldGhvZCA9ICJJQkNGIiwgcGFyYW09bGlzdChtZXRob2Q9IkNvc2luZSIsIGs9MzAsIG5vcm1hbGl6ZSA9IE5VTEwsIG5hX2FzX3plcm8gPSBUUlVFKSkgI25vcm1hbGl6ZSA9ICdjZW50ZXInLCAnWi1zY29yZScNCg0Kc2hvd19jb3ZlcmFnZSA8LSBmdW5jdGlvbihsaXN0T2ZEaWZmZXJlbnROLCByZWNvbW1lbmRlcikgew0KICANCiAgbGlzdE9mQ292ZXJhZ2VzIDwtIHZlY3RvcigpDQogIGZvciAoTiBpbiBsaXN0T2ZEaWZmZXJlbnROKSB7DQoNCiAgICAjIHByZWRpY3QgdG9wIE4gbW92aWVzDQogICAgcHJlIDwtIHByZWRpY3QocmVjLCB0cmFpbiwgbiA9IE4pDQogICAgcmVjb19saXN0IDwtIGFzKHByZSwgImxpc3QiKQ0KICAgIHJlY29tbWVuZGF0aW9ucyA8LSBhcy5kYXRhLmZyYW1lKHJlY29fbGlzdCkNCiAgICBhbGxfcmVjb21tZW5kYXRpb25zIDwtIGxpc3QoKQ0KICAgIA0KICAgICMgZmluZCB0cnVlIHBvc2l0aXZlcyBhbmQgZmFsc2UgcG9zaXRpdmVzIGZvciBhbGwgdXNlcnMgYW5kIGFkZCB0aGVtIHVwDQogICAgZm9yIChpIGluIGNvbG5hbWVzKHJlY29tbWVuZGF0aW9ucykpIHsNCiAgICAgIGFsbF9yZWNvbW1lbmRhdGlvbnMgPC0gYXBwZW5kKGFsbF9yZWNvbW1lbmRhdGlvbnMsIGRwbHlyOjpwdWxsKHJlY29tbWVuZGF0aW9uc1tpXSkpDQogICAgfQ0KDQogICAgDQogICAgbGlzdE9mQ292ZXJhZ2VzIDwtIGMobGlzdE9mQ292ZXJhZ2VzLCByb3VuZChsZW5ndGgodW5pcXVlKGFsbF9yZWNvbW1lbmRhdGlvbnMpKSAvIGRpbSh0cmFpbilbMl0sIGRpZ2l0cyA9IDQpKQ0KICB9DQogIHJldHVybiAoZGF0YS5mcmFtZShOID0gbGlzdE9mRGlmZmVyZW50TiwgY292ZXJhZ2UgPSBsaXN0T2ZDb3ZlcmFnZXMpKQ0KfQ0KDQpkZl9jb3ZlcmFnZSA8LSBzaG93X2NvdmVyYWdlKGMoNSwxMCwxNSwyMCwyNSwzMCksIHJlYykNCmRmX2NvdmVyYWdlDQpgYGANClN1bW1lIGFsbGVyIHVudGVyc2NoaWVkbGljaGVuIFByb2R1a3RlLCB3ZWxjaGUgaW4gZGVuIFRvcC1OIExpc3RlbiBhbGxlciBLdW5kKklubmVuIGluZ2VzYW10IGF1ZnRhdWNoZW4gZGl2aWRpZXJ0IGR1cmNoIGRpZSBNZW5nZSBhbGxlciBQcm9kdWt0ZS4NCg0KKioqDQojIyMjIFN5c3RlbS1sZXZlbCBub3ZlbHR5DQpgYGB7cn0NCiMgdHJhaW4gcmVjb21tZW5kZXINCnJlYyA8LSBSZWNvbW1lbmRlcih0cmFpbiwgbWV0aG9kID0gIklCQ0YiLCBwYXJhbT1saXN0KG1ldGhvZD0iQ29zaW5lIiwgaz0zMCwgbm9ybWFsaXplID0gTlVMTCwgbmFfYXNfemVybyA9IFRSVUUpKQ0KDQoNCnNob3dfbm92ZWx0eSA8LSBmdW5jdGlvbihsaXN0T2ZEaWZmZXJlbnROLCByZWNvbW1lbmRlcikgew0KICAjIGNyZWF0ZSBhIGRhdGFzZXQgd2l0IGNhbGN1bGF0ZWQgcG9wdWxhcml0eSBmb3IgZXZlcnkgbW92aWUNCiAgcG9wdWxhcml0eSA8LSBhcyhNb3ZpZUxlbnNlLCAiZGF0YS5mcmFtZSIpDQogIHBvcHVsYXJpdHkgPC0gcG9wdWxhcml0eSAlPiUNCiAgICBncm91cF9ieShpdGVtKSAlPiUgDQogICAgc3VtbWFyaXplKHJhdGluZ3MgPSBuKCkgLyBkaW0oTW92aWVMZW5zZSlbMl0pICU+JSANCiAgICBtdXRhdGUocmF0aW5ncyA9IGxvZzIocmF0aW5ncykpDQogIA0KICBsaXN0T2ZOb3ZlbHRpZXMgPC0gdmVjdG9yKCkNCiAgZm9yIChOIGluIGxpc3RPZkRpZmZlcmVudE4pIHsNCiAgICAjIGdldCB0b3AtTi1saXN0IGZvciBhIGNlcnRhaW4gTg0KICAgIHByZSA8LSBwcmVkaWN0KHJlYywgdHJhaW4sIG4gPSBOKQ0KICAgIHJlY29fbGlzdCA8LSBhcyhwcmUsICJsaXN0IikNCiAgICByZWNvbW1lbmRhdGlvbnMgPC0gYXMuZGF0YS5mcmFtZShyZWNvX2xpc3QpDQogICAgDQogICAgDQogICAgdG90YWxfbm92ZWx0eSA8LSB2ZWN0b3IoKQ0KICAgIGZvciAoaSBpbiBjb2xuYW1lcyhyZWNvbW1lbmRhdGlvbnMpKSB7DQogICAgICAjIGNhbGN1bGF0ZSBtZWFuIHBvcHVsYXJpdHkgb2YgcmVjb21tZW5kZWQgaXRlbXMgZm9yIHVzZXINCiAgICAgIHJlY28gPC0gcmVjb21tZW5kYXRpb25zW2ldDQogICAgICBjb2xuYW1lcyhyZWNvKVsxXSA8LSAiaXRlbSINCiAgICAgIHJlY28gPC0gaW5uZXJfam9pbihwb3B1bGFyaXR5LCByZWNvLCBieSA9ICdpdGVtJykNCiAgICAgIG5vdmVsdHkgPC0gbWVhbihhcy5udW1lcmljKHJlY28kcmF0aW5ncykpDQogICAgICB0b3RhbF9ub3ZlbHR5IDwtIGModG90YWxfbm92ZWx0eSwgbm92ZWx0eSkNCiAgICB9DQogICAgbGlzdE9mTm92ZWx0aWVzIDwtIGMobGlzdE9mTm92ZWx0aWVzLCAwIC0gbWVhbih0b3RhbF9ub3ZlbHR5KSkNCiAgfQ0KICByZXR1cm4gKGRhdGEuZnJhbWUoTiA9IGxpc3RPZkRpZmZlcmVudE4sIG5vdmVsdHkgPSBsaXN0T2ZOb3ZlbHRpZXMpKQ0KfQ0KDQpkZl9ub3ZlbHR5IDwtIHNob3dfbm92ZWx0eShjKDUsMTAsMTUsMjAsMjUsMzApLCByZWMpDQpkZl9ub3ZlbHR5DQpgYGANCk1pdHRlbCBkZXIgU2hhbm5vbiBJbmZvcm1hdGlvbiBkZXIgUG9wdWxhcml0w6R0IGRlciBQcm9kdWt0ZSBpbiBkZXIgVG9wLU4gTGlzdGUgZ2VtaXR0ZWx0IMO8YmVyIGFsbGUgS3VuZCpJbm5lbi4gDQoNCg0KDQoNCmBgYHtyfQ0KDQppbWFnZShhcyhyZWNAbW9kZWwkc2ltLCAicmVhbFJhdGluZ01hdHJpeCIpKQ0KI3NpbWlsYXJpdHkNCg0KYGBgDQoNCg0KYGBge3J9DQoNCiNpbWFnZShhcyhzaW1pbGFyaXR5KHRyYWluLCBtZXRob2QgPSAiQ29zaW5lIiwgd2hpY2ggPSAiaXRlbXMiKSwgIm1hdHJpeCIpKQ0KDQojIHBsb3RTaW1pbGFyaXR5TWF0cml4KHRyYWluLCB5ID0gTlVMTCwgY2x1c0xhYmVscyA9IE5VTEwsIGNvbFggPSBOVUxMLCBjb2xZID0gTlVMTCwgbXlMZWdlbmQgPSBOVUxMLCBmaWxlTmFtZSA9ICJwb3N0ZXJpb3JTaW1pbGFyaXR5TWF0cml4Iiwgc2F2ZVBORyA9IEZBTFNFLCBzZW1pU3VwZXJ2aXNlZCA9IEZBTFNFLCBzaG93T2JzTmFtZXMgPSBGQUxTRSwgY2xyID0gRkFMU0UsIGNsYyA9IEZBTFNFLCBwbG90V2lkdGggPSA1MDAsIHBsb3RIZWlnaHQgPSA0NTApDQoNCmBgYA0KDQoNCg0KYGBge3J9DQoNCmNvc2luZV9zaW0gPC0gZnVuY3Rpb24oQSwgQikNCnsNCiAgc2ltaWxhcml0eSA8LSBBICUqJSBCIC8gKG5vcm0oQSwgdHlwZT0iMiIpICogbm9ybShCLCB0eXBlPSIyIikpDQogIHJldHVybihzaW1pbGFyaXR5KQ0KfQ0KDQpqYWNjYXJkX3NpbSA8LSBmdW5jdGlvbihBLCBCKQ0Kew0KICBpbnRlciA9IGxlbmd0aChpbnRlcnNlY3QoQSwgQikpDQogIHVuaW9uID0gbGVuZ3RoKEEpICsgbGVuZ3RoKEIpIC0gaW50ZXINCiAgamFjID0gaW50ZXIgLyB1bmlvbg0KICByZXR1cm4gKGphYykNCn0NCg0KDQpBIDwtIGMoNSwgMywgMiwgMSkNCkIgPC0gYygxLCAyLCAzLCA0KQ0KDQpjb3NpbmVfc2ltKEEsIEIpDQpqYWNjYXJkX3NpbShBLCBCKQ0KI2xpYnJhcnkobHNhKQ0KI2Nvc2luZShBLCBCKQ0KDQpgYGANCg0KYGBge3J9DQpzaW1pbGFyaXR5IDwtIGFzLm1hdHJpeChyZWNAbW9kZWwkc2ltKQ0KZGltKHNpbWlsYXJpdHkpDQpgYGANCg0KDQpgYGB7cn0NCndpZGVfbWF0cml4IDwtIGFzLm1hdHJpeChzdWJzZXQobW92aWVzX3dpZGVyLCBzZWxlY3QgPSAtYyh1c2VyKSkpDQoNCiMgcmVwbGFjZSBuYXMgd2l0aCAwIChubyBhZGp1c3RlZCBjb3NpbmUgc2ltaWxhcml0eSkNCndpZGVfbWF0cml4W2lzLm5hKHdpZGVfbWF0cml4KV0gPC0gMA0KDQojIGliY2YsIGJlY2F1c2UgY29sdW1ucyBhcmUgdGFrZW4gaGVyZQ0KIyByb3cgY291bnQNCmxlbiA8LSBkaW0od2lkZV9tYXRyaXgpWzJdDQpyZXMgPC0gZGlhZyhsZW4pDQoNCmZvcihpIGluIDE6bGVuKQ0Kew0KICBmb3IoaiBpbiAxOmxlbikNCiAgew0KICAgIGlmKGkgPCBqICYgaSAhPSBqKQ0KICAgIHsNCiAgICAgIHJlc1tpLGpdIDwtIGNvc2luZV9zaW0od2lkZV9tYXRyaXhbLGldLCB3aWRlX21hdHJpeFssal0pDQogICAgICByZXNbaixpXSA8LSByZXNbaSxqXQ0KICAgIH0NCiAgfQ0KfQ0KcmVzWzE6MTAsIDE6MTBdDQoNCiNkaW0od2lkZV9tYXRyaXgpDQoNCmBgYA0KDQoNCg0KYGBge3J9DQojY29zaW5lX3NpbSh3aWRlX21hdHJpeFssMV0sIHdpZGVfbWF0cml4WywyXSkNCiN3aWRlX21hdHJpeFsyLDFdDQojYXMubWF0cml4KHN1YnNldChtb3ZpZXNfd2lkZXIsIHNlbGVjdCA9IC1jKHVzZXIpKSlbLDJdDQoNCmRmX3JlcyA8LSBhcy5kYXRhLmZyYW1lKHJlcykNCmRmX3Jlcw0KDQppbWFnZShhcyhkZl9yZXMsICJyZWFsUmF0aW5nTWF0cml4IikpDQphcyhkZl90ZXN0LCAncmVhbFJhdGluZ01hdHJpeCcpDQojZ2dwbG90KGRmX3JlcywgYWVzKHggPSB4X3ZhcmlhYmxlLCB5ID0geV92YXJpYWJsZSkpICsgc3RhdF9kZW5zaXR5MmQoYWVzKGZpbGwgPSAuLmRlbnNpdHkuLiksIGNvbnRvdXIgPSBGLCBnZW9tID0gJ3RpbGUnKQ0KDQpgYGANCg0KDQpgYGB7cn0NCiNnZ3Bsb3QoZGZfcmVzLCBhZXMoeD1WMSwgeT1WMikgKSArDQojICBnZW9tX2JpbjJkKCkgKw0KIyAgdGhlbWVfYncoKQ0KcmVxdWlyZShsYXR0aWNlKQ0KbGV2ZWxwbG90KHJlcykNCmBgYA0KDQpgYGB7cn0NCndpZGVfbWF0cml4IDwtIGFzLm1hdHJpeChzdWJzZXQobW92aWVzX3dpZGVyLCBzZWxlY3QgPSAtYyh1c2VyKSkpDQoNCiMgcmVwbGFjZSBuYXMgd2l0aCAwIChubyBhZGp1c3RlZCBjb3NpbmUgc2ltaWxhcml0eSkNCiN3aWRlX21hdHJpeFtpcy5uYSh3aWRlX21hdHJpeCldIDwtIDANCg0KIyBpYmNmLCBiZWNhdXNlIGNvbHVtbnMgYXJlIHRha2VuIGhlcmUNCiMgcm93IGNvdW50DQpsZW4gPC0gZGltKHdpZGVfbWF0cml4KVsyXQ0KcmVzIDwtIGRpYWcobGVuKQ0KDQpmb3IoaSBpbiAxOmxlbikNCnsNCiAgZm9yKGogaW4gMTpsZW4pDQogIHsNCiAgICBpZihpIDwgaiAmIGkgIT0gaikNCiAgICB7DQogICAgICByZXNbaSxqXSA8LSBqYWNjYXJkX3NpbSh3aWRlX21hdHJpeFssaV0sIHdpZGVfbWF0cml4WyxqXSkNCiAgICAgIHJlc1tqLGldIDwtIHJlc1tpLGpdDQogICAgfQ0KICB9DQp9DQpyZXNbMToxMCwgMToxMF0NCg0KI2RpbSh3aWRlX21hdHJpeCkNCg0KYGBgDQoNCmBgYHtyfQ0KbGV2ZWxwbG90KHJlcykNCmBgYA0KDQoNCg0KDQojIyMjIyMgU1BpZWx3aWVzZQ0KYGBge3J9DQoNCmdncGxvdChtb3ZpZXMsIGFlcyh4PWl0ZW0sIHk9dXNlciwgY29sb3VyPXJhdGluZykpICsgZ2VvbV9wb2ludChhbHBoYT0xLCBzaXplID0gMC4wNSkgKyB0aGVtZV9jbGFzc2ljKCkNCg0KYGBgDQoNCg0KDQoNCg0K